题目描述

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

1. 首先，选择一个位置开始，顺时针地将数字和符号分别记在数组 $ A $ 和数组 $ C $ 中；
2. $ B_0 = A_0 $
3. 当 $ x > 0 $（$ x $ 为下标值）时：
   • 若 $ C_x $ 为 +，$ B_x = (Ax + A{x - 1}) \bmod 10 $；
   • 若 $ C_x $ 为 *，$ B_x = (Ax \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 $。

样例

input

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

output

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 $