题目描述

在一个确定性的抢椅子游戏中，有 $n$ 把椅子按圆形摆放。椅子按顺时针方向从 $1$ 到 $n$ 编号。 一开始，第 $i$ 个玩家坐在第 $i$ 把椅子上。

在游戏过程中，主持人会同时对所有玩家发布指令。

指令类型

有两种移动指令，以及一种查询指令：

1. 加法移动指令：+ x 这条指令表示： 每个玩家从当前的椅子 $i$ 移动到椅子 $i + x$。

2. 乘法移动指令：* x 这条指令表示： 每个玩家从当前的椅子 $i$ 移动到椅子 $i \cdot x$。

3. 查询指令：? x 这条指令表示： 询问当前坐在椅子 $x$ 上的是哪一位玩家。

所有上述计算都在模 $n$ 意义下进行，也就是说：

• 计算 $i + x$ 或 $i \cdot x$ 后，对 $n$ 取模；
• 若得到的余数为 $0$，则对应的是第 $n$ 把椅子。

冲突规则（多名玩家想坐同一把椅子）

如果在一次移动中，有两个或以上的玩家要移动到同一把椅子，则：

• 比较这些玩家从各自原椅子顺时针走到目标椅子的“顺时针距离”；
• 顺时针距离最小的玩家能成功坐下该椅子；
• 其他也试图坐该椅子的玩家则会被淘汰出局，不再继续参与后续的游戏。

例如，在上图中（大圆代表椅子，小圆代表玩家），下一条指令是 * 10：

• 玩家 10（当前坐在椅子 11）和玩家 4（当前坐在椅子 5）都要移动到椅子 2；
• 由于玩家 10 顺时针走到椅子 2 的距离更短，因此玩家 10 获得该座位；
• 玩家 4 则被淘汰。 其它 10 位玩家也会各自移动到相应的椅子上，但为了便于阅读，图中省略了这些细节。

由于游戏过程是确定性的，大家已经没有兴趣继续玩下去了，现在需要你来根据给出的指令模拟游戏的过程。

输入格式

输入包含：

• 一行两个整数 $n,q(2 \le n, q \le 5 \cdot 10^5)$，分别表示椅子的数量和指令的数量；

• 接下来 $q$ 行，每行是一条指令，形式如下三种之一：

  • + x：玩家从椅子 $i$ 移动到椅子 $i + x$（模 $n$）；
  • * x：玩家从椅子 $i$ 移动到椅子 $i \cdot x$（模 $n$）；
  • ? x：询问当前坐在椅子 $x$ 上的是哪位玩家。

保证所有的 $x$ 都满足 $1 \leq x \leq n$。

输出格式

对于每一条查询指令 ? x，输出一行结果：

• 如果椅子 $x$ 上当前有人，则输出该玩家的编号；
• 如果椅子 $x$ 目前空着，则输出 -1。

输入输出样例 #1

输入 #1

12 10
? 12
+ 1
? 12
* 10
? 2
* 5
? 2
* 6
? 1
? 12

输出 #1

12
11
10
6
-1
11

输入输出样例 #2

输入 #2

32 11
* 6
? 8
* 6
+ 31
* 28
? 4
+ 1
* 2
+ 1
* 3
? 1

输出 #2

28
32
32