레이팅 미적용In a deterministic version of Musical ChairsYou do not need to know the original game, but you can try to play it after the contest is over., there are \(n\) chairs placed in a circle. The chairs are numbered from \(1\) to \(n\) in clockwise order. Initially, the \(i\)th player sits on the \(i\)th chair. During the game, the game master gives commands to all players at once.
The first type of command tells each player to move \(x\) chairs farther in clockwise order, so they must move from chair \(i\) to chair \(i+x\).
The second type of command tells each player to move from chair \(i\) to chair \(i\cdot{}x\). Both these calculations are done modulo \(n\), where a remainder of \(0\) corresponds to chair \(n\).
If two or more people want to move to the same chair, then the player needing to travel the least in clockwise direction to reach the chair gets to take the seat, and the other players trying to reach the same chair are out of the game. This is illustrated in Figure , where the larger circles represent the chairs and their numbers are written on their inside. The smaller circles represent the players. The next command (* 10) tells player \(10\) (now on seat \(11\)) and player \(4\) (now on seat \(5\)) to move to chair \(2\). However, since player \(10\) needs to travel less, this player gets to take the seat. Note that the other \(10\) players will also move to some other chairs, but this is omitted from the figure for the sake of readability.
The jury wasted most of their free time designing this game and now need to go back to work. Fortunately, the game is deterministic, so you can play the game without the help of the jury.
The input consists of:
- One line with two integers \(n\) and \(q\) (\(2\leq n,q\leq5\cdot10^5\)), the number of chairs and the number of commands.
- \(q\) lines, each containing one of three command types:
[topsep=0pt, itemsep=-2pt]
- "+ \(x\)": The player on chair \(i\) moves to chair \(i+x\).
- "* \(x\)": The player on chair \(i\) moves to chair \(i\cdot{}x\).
- "? \(x\)": Tell us the number of the player on chair \(x\).
All of the values \(x\) will satisfy \(1 \leq x \leq n\).
For each command of type '?', output the number of the player on the requested chair. If the chair is currently empty, output \(-1\) instead.
12 10
? 12
+ 1
? 12
* 10
? 2
* 5
? 2
* 6
? 1
? 12
12
11
10
6
-1
11
32 11
* 6
? 8
* 6
+ 31
* 28
? 4
+ 1
* 2
+ 1
* 3
? 1
28
32
32