Description

在一个确定性的“抢椅子”游戏中，有 $n$ 把椅子围成一圈，椅子按顺时针方向编号为 $1$ 到 $n$。最初，第 $i$ 个玩家坐在第 $i$ 把椅子上。在游戏过程中，主持人会同时向所有玩家发出指令。

:::align{center} 一家人在玩抢椅子。图片作者 Artaxerxes，CC BY-SA 3.0，来源于 Wikimedia Commons。 :::

第一种指令要求每个玩家顺时针移动 $x$ 把椅子，即从椅子 $i$ 移动到椅子 $i+x$。

第二种指令要求每个玩家从椅子 $i$ 移动到椅子 $i\cdot x$。

上述两种操作均在模 $n$ 意义下进行，余数为 $0$ 时视为第 $n$ 把椅子。

如果有两名或以上的玩家试图移动到同一把椅子，则顺时针方向上需要移动距离最短的玩家获得该椅子，其余玩家被淘汰。下图 C.1 进行了说明：大圆圈表示椅子，内部数字为椅子编号，小圆圈表示玩家。下一个指令（$\texttt{* 10}$）要求现在在椅子 $11$ 的玩家 $10$ 和在椅子 $5$ 的玩家 $4$ 都移动到椅子 $2$。由于玩家 $10$ 顺时针需要移动的距离更短，因此他获得该椅子。注意，其他 $10$ 名玩家也会移动到其它椅子，但为了便于阅读，图中未画出。

:::align{center} 图 C.1：样例输入 1 的第四条指令示意图，玩家 $4$ 和 $10$ 都要移动到椅子 $2$，但玩家 $10$ 顺时针移动距离更短，因此他获得该椅子。 :::

出题人已经花了大量时间设计这个游戏，现在需要回去工作。幸运的是，这个游戏是确定性的，所以你可以不用出题人也能玩。

$^1$你不需要了解原始的抢椅子游戏，但比赛结束后可以试着玩一玩。

Input Format

输入包含：

• 一行两个整数 $n$ 和 $q$（$2\leq n,q\leq5\cdot10^5$），分别表示椅子的数量和指令的数量。
• 接下来 $q$ 行，每行包含以下三种指令之一：
  • “$\texttt{+ x}$”：坐在椅子 $i$ 的玩家移动到椅子 $i+x$。
  • “$\texttt{* x}$”：坐在椅子 $i$ 的玩家移动到椅子 $i\cdot x$。
  • “$\texttt{? x}$”：询问当前坐在椅子 $x$ 上的玩家编号。

所有 $x$ 满足 $1 \leq x \leq n$。

Output Format

对于每个“$\texttt{?}$”类型的指令，输出当前坐在指定椅子上的玩家编号。如果该椅子上没有玩家，输出 $-1$。

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

Hint

由 ChatGPT 4.1 翻译