题目描述
小凸得到了一个密码盘，密码盘被等分成 $N$ 个扇形，每个扇形上有一个数字（$0 \sim 9$），和一个符号（$+$ 或 $*$），密码盘解密的方法如下：

首先，选择一个位置开始，顺时针地将数字和符号分别记在数组 $A$ 和数组 $C$ 中；
$B_0 = A_0$
当 $x > 0$（$x$ 为下标值）时：

• 若 $C_x$ 为 $+$，$B_x = (A_x + A_{x - 1}) \bmod 10$；
• 若 $C_x$ 为 $*$，$B_x = (A_x \times A_{x - 1}) \bmod 10$；

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

现在小凸得到了一份指令表，指令表上有 $2$ 种操作。

一种指令是修改操作，即改变原来密码盘上一个位置的数字和符号；
另一种指令是询问操作，具体如下：

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

输入格式
第一行包含两个整数 $n$、$m$，代表密码盘大小和指令个数。
接下来 $n$ 行，每行包含一个整数和一个字符，按顺时针顺序给出了密码盘上的数组和符号。
接下来 $m$ 行，依次给出指令。

每行第一个整数代表指令类型：

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

密码盘上的位置标号为 $0$ 到 $n - 1$。

输出格式
对于每个询问操作，输出一行答案，若答案环上没有 $0$，输出 $-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$ 个询问，答案环为 $\{ 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$。

数据范围与提示
$5 \leq n, m \leq 10^5$