#59. [SCOI 2015] 小凸解密码

小凸得到了一个密码盘，密码盘被等分成 个扇形，每个扇形上有一个数字 ，和一个符号 + 或 * 。密码盘解密的方法如下：

首先，选择一个位置开始，顺时针地将数字和符号分别记在数组 和数组 中。解密的方法如下：

• 当 时：
• 若 为 +，
• 若 为 *，

操作完成后，可以得到一个长度为 的数组 ，然后以 为起点将 数组顺时针写成一个环，解密就完成了，称得到的环为答案环。

现在小凸得到了一份指令表，指令表上有 2 种操作。一种指令是修改操作，即改变原来密码盘上一个位置的数字和符号。另一种指令是询问操作，具体如下：

• 首先从指令给出的位置开始完成解密，得到答案环。
• 答案环上会有一些 连在一起，将这些连在一起的 称为零区间，找出其中距离 最远的那个零区间，输出这个距离（零区间和 的距离定义为：零区间内所有 到 距离中的最小值）。

第一行包含两个整数 ，代表密码盘大小和指令个数。

接下来 行，每行包含一个整数和一个字符，按顺时针顺序给出了密码盘上的数组和符号。

接下来 行，依次给出指令。每行第一个整数代表指令类型：

• 若第一个整数为 1，代表本行对应指令为修改操作，之后依次有两个整数 和一个字符 ，分别代表修改的位置，以及修改后该位置的数字和字符。
• 若第一个整数为 2，代表本行对应指令位询问操作，之后有一个整数 ，代表本次操作中解密的开始位置。

密码盘上的位置标号为 到 。

数据保证合法，即数据中 ， 为 + 或 *。

对于每个询问操作 行，输出答案，若答案环上没有 ，输出 -1。

样例输入

5 8
0 *
0 *
0 *
0 *
0 *
2 0
1 0 1 +
1 2 1 +
2 3
1 1 1 +
1 3 1 +
1 4 1 +
2 4

样例输出

0
2
-1

样例解释：

对于第 个询问，答案环为 ，仅有 个零区间，且 在其中，所以距离是 。

对于第 个询问，答案环为 ，有 个零区间， 和 距离是 ， 和 距离是 ，故答案为 。

对于第 个询问，答案环为 ，没有零区间，答案是 ?1。

数据范围：

• 对于 数据，；
• 对于 数据，；
• 对于 数据，。