Problem C
Chair Dance

A family playing Musical Chairs.
CC BY-SA 3.0 by Artaxerxes on Wikimedia Commons

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 1, 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.

Figure 1: Illustration of Sample Input 1 at the fourth command, where players $4$ and $10$ need to move to chair $2$. Because player $10$ needs to travel less in clockwise direction, this player gets to take the seat.

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.

Input

The input consists of:

• One line with two integers $n$ and $q$ ($2\leq n,q\leq 5\cdot 10^5$), the number of chairs and the number of commands.

• $q$ lines, each containing one of three command types:

  • “+ $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$.

Output

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