30900번 - Chair Dance 다국어

문제

In a deterministic version of Musical Chairs¹, 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 C.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 C.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.

¹You do not need to know the original game, but you can try to play it after the contest is over.

입력

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

제한

힌트