Problem Description

Xiao Tu obtained a password dial. The dial is evenly divided into $n$ sectors. Each sector contains a digit $(0 \sim 9)$ and a symbol ($+$ or $*$). The decryption method is as follows.

First, choose a starting position, and record the digits and symbols clockwise into arrays $A$ and $C$, respectively. The decryption is done as follows:

• $B_0 = A_0$.
• When $x > 0$:
  • If $C_x$ is +, then $B_x = (A_x + A_{x - 1}) \% 10$.
  • If $C_x$ is *, then $B_x = (A_x \times A_{x - 1}) \% 10$.

After finishing the operations, you obtain an array $B$ of length $n$. Then, starting from $B_0$, write the array $B$ clockwise into a ring. The decryption is complete. The resulting ring is called the answer ring.

Now Xiao Tu has an instruction list with 2 types of operations. One type is an update operation, which changes the digit and symbol at a position on the original dial. The other type is a query operation, described as follows:

• First, start from the position given in the instruction and complete the decryption to obtain the answer ring.
• On the answer ring, there may be some consecutive $0$’s. Such consecutive $0$’s are called a zero interval. Find the zero interval that is farthest from $B_0$, and output this distance (the distance between a zero interval and $B_0$ is defined as the minimum, among all $0$’s in the interval, of the distance from that $0$ to $B_0$).

Input Format

The first line contains two integers $n, m$, representing the size of the password dial and the number of instructions.

The next $n$ lines each contain an integer and a character, giving the digit array and symbol array on the dial in clockwise order.

The next $m$ lines give the instructions in order. The first integer on each line indicates the instruction type:

• If the first integer is 1, this instruction is an update operation. It is followed by two integers $pos, num$ and a character $\rm opt$, representing the position to modify, and the digit and character at that position after modification.
• If the first integer is 2, this instruction is a query operation. It is followed by an integer $pos$, representing the starting position for decryption in this operation.

The positions on the dial are numbered from $0$ to $n - 1$.

The testdata is guaranteed to be valid, i.e., $0 \leq pos < n$, $0 \leq num \leq 9$, and $\rm opt$ is + or *.

Output Format

For each query operation, output one line with the answer. If there is no $0$ on the answer ring, output −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

Hint

Sample Explanation:

For the $1$st query, the answer ring is $\{0, 0, 0, 0, 0\}$. There is only $1$ zero interval, and $B_0$ is inside it, so the distance is $0$.
For the $2$nd query, the answer ring is $\{0, 0, 1, 0, 1\}$. There are $2$ zero intervals. The distance between $[0, 1]$ and $B_0$ is $0$, and the distance between $[3, 3]$ and $B_0$ is $2$, so the answer is $2$.
For the $3$rd query, the answer ring is $\{1, 2, 2, 2, 2\}$. There is no zero interval, so the answer is −1.

Constraints:

For $20\%$ of the testdata, $5 \leq n \leq 10^5$, $5 \leq m \leq 1000$.
For $60\%$ of the testdata, $5 \leq n \leq 10^5$, $5 \leq m \leq 10^4$.
For $100\%$ of the testdata, $5 \leq n, m \leq 10^5$.

Translated by ChatGPT 5