P5226 [SCOI2015] Xiao Tu Solves the Password

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$).

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 `*`.

For each query operation, output one line with the answer. If there is no $0$ on the answer ring, output `−1`.

**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