P5226 [SCOI2015] 小凸解密码

小凸得到了一个密码盘，密码盘被等分成 $n$ 个扇形，每个扇形上有一个数字 $(0 \sim 9)$，和一个符号 $($ `+` 或 `*` $)$。密码盘解密的方法如下： 首先，选择一个位置开始，顺时针地将数字和符号分别记在数组 $A$ 和数组 $C$ 中。解密的方法如下： - $B_0 = A_0$ - 当 $x > 0$ 时： - 若 $C_x$ 为 `+`，$B_x = (A_x + A_{x - 1}) \% 10$ - 若 $C_x$ 为 `*`，$B_x = (A_x \times A_{x - 1}) \% 10$ 操作完成后，可以得到一个长度为 $n$ 的数组 $B$，然后以 $B_0$ 为起点将 $B$ 数组顺时针写成一个环，解密就完成了，称得到的环为答案环。 现在小凸得到了一份指令表，指令表上有 2 种操作。一种指令是修改操作，即改变原来密码盘上一个位置的数字和符号。另一种指令是询问操作，具体如下： - 首先从指令给出的位置开始完成解密，得到答案环。 - 答案环上会有一些 $0$ 连在一起，将这些连在一起的 $0$ 称为零区间，找出其中距离 $B_0$ 最远的那个零区间，输出这个距离（零区间和 $B_0$ 的距离定义为：零区间内所有 $0$ 到 $B_0$ 距离中的最小值）。

无

无

**样例解释：** 对于第 $1$ 个询问，答案环为 $\{0, 0, 0, 0, 0\}$，仅有 $1$ 个零区间，且 $B_0$ 在其中，所以距离是 $0$。 对于第 $2$ 个询问，答案环为 $\{0, 0, 1, 0, 1\}$，有 $2$ 个零区间，$[0, 1]$ 和 $B_0$ 距离是 $0$，$[3, 3]$ 和 $B_0$ 距离是 $2$，故答案为 $2$。 对于第 $3$ 个询问，答案环为 $\{1, 2, 2, 2, 2\}$，没有零区间，答案是 `−1`。 **数据范围：** 对于 $20 \%$ 数据，$5 \leq n \leq 10^5, 5 \leq m \leq 1000$； 对于 $60 \%$ 数据，$5 \leq n \leq 10^5, 5 \leq m \leq 10^4$； 对于 $100 \%$ 数据，$5 \leq n, m \leq 10^5$。