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

一家人正在玩抢椅子游戏。

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

第二种指令要求每位玩家从椅子 $i$ 移动到椅子 $i \cdot x$。以上两种计算均在模 $n$ 下进行，其中余数为 $0$ 对应椅子 $n$。

如果两名或多名玩家想要移动到同一把椅子，那么需要顺时针移动距离最短的玩家获得该座位，而其他试图到达同一椅子的玩家将被淘汰出局。图 C.1 展示了这一过程，其中较大的圆圈代表椅子，内部写有椅子编号。较小的圆圈代表玩家。下一条指令（$* 10$）要求玩家 $10$（当前在座位 $11$）和玩家 $4$（当前在座位 $5$）移动到椅子 $2$。然而，由于玩家 $10$ 需要移动的距离更短，因此该玩家获得了座位。注意，其他 $10$ 位玩家也会移动到其他椅子上，但为了图示清晰，图中省略了这些移动。

图 C.1：第四条指令时样例输入 1 的示意图，玩家 4 和 10 需要移动到椅子 2。因为玩家 10 在顺时针方向上需要移动的距离更短，所以该玩家获得了座位。

裁判组在设计这个游戏上浪费了大部分空闲时间，现在需要回去工作了。幸运的是，这个游戏是确定性的，所以你可以在没有裁判帮助的情况下进行游戏。

输入格式

输入包含： 一行包含两个整数 $n$ 和 $q$ ($2 \le n, q \le 5 \cdot 10^5$)，分别表示椅子的数量和指令的数量。 $q$ 行，每行包含以下三种指令类型之一： “$+ x$”：在椅子 $i$ 上的玩家移动到椅子 $i + x$。 “$* x$”：在椅子 $i$ 上的玩家移动到椅子 $i \cdot x$。 * “$? x$”：询问在椅子 $x$ 上的玩家编号。 所有值 $x$ 均满足 $1 \le x \le n$。

输出格式

对于每个“$?”$ 类型的指令，输出请求椅子上的玩家编号。如果该椅子当前为空，则输出 $-1$。

样例

输入格式 1

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

输出格式 1

12
11
10
6
-1
11

输入格式 2

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

输出格式 2

28
32
32