P13702 [NWERC 2023] Chair Dance

在一个确定性的“抢椅子”游戏中，有 $n$ 把椅子围成一圈，椅子按顺时针方向编号为 $1$ 到 $n$。最初，第 $i$ 个玩家坐在第 $i$ 把椅子上。在游戏过程中，主持人会同时向所有玩家发出指令。  :::align{center} 一家人在玩抢椅子。图片作者 Artaxerxes，CC BY-SA 3.0，来源于 [Wikimedia Commons](https://commons.wikimedia.org/wiki/File:Musical_chairs_Lawn_Jam_Our_Community_Place_Harrisonburg_VA_June_2008.jpg)。 ::: 第一种指令要求每个玩家顺时针移动 $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$你不需要了解原始的抢椅子游戏，但比赛结束后可以试着玩一玩。

输入包含： - 一行两个整数 $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$。

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

由 ChatGPT 4.1 翻译