题目描述

In a deterministic version of Musical Chairs$^1$, 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.

:::align{center} 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 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 ($\texttt{* 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.

:::align{center} 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.

$^1$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:

  • "$\texttt{+ x}$": The player on chair $i$ moves to chair $i+x$.
  • "$\texttt{* x}$": The player on chair $i$ moves to chair $i\cdot{}x$.
  • "$\texttt{? 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 '$\texttt{?}$', 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