Decrypting the Password Dial Ring

You are given a circular password dial divided into \(n\) equal sectors. Each sector contains a digit (from 0 to 9) and an operator (either \( + \) or \( * \)). The dial is used to decrypt a secret message using the following procedure:

1. Select a starting position and list the digits and operators from that position in clockwise order to form arrays \(A\) and \(C\). (Note: The operator at index 0, \(C_0\), is provided but not used in the computation.)
2. Construct an array \(B\) of length \(n\) as follows:
   \(B_0 = A_0\)
   For \(1 \le x < n\):
   \(B_x = \begin{cases} (A_x + A_{x-1}) \mod 10, & \text{if } C_x = '+' \\ (A_x \times A_{x-1}) \mod 10, & \text{if } C_x = '*'. \end{cases}\)
3. The array \(B\) is then written as a ring starting from \(B_0\). In this ring, a contiguous group of one or more zeros is called a zero interval.
4. The distance of a zero interval from \(B_0\) is defined as the minimum index (distance) among the zeros in that interval when traversing the ring in order (with \(B_0\) at distance 0).
5. Finally, the answer for the decryption is the distance of the zero interval that is farthest from \(B_0\).

In addition, the dial supports two types of operations:

• Modification operation: Update the digit and operator at a specified position.
• Query operation: Given a starting position, perform the decryption procedure described above and print the required distance.

inputFormat

The input begins with a line containing two integers \(n\) and \(q\) \((1 \le n, q \le 10^5)\), representing the number of sectors on the dial and the number of operations, respectively.

The second line contains \(n\) space-separated digits \(A_0, A_1, \ldots, A_{n-1}\) (each between 0 and 9), which are the initial digits of the dial.

The third line contains \(n\) space-separated characters, each either + or *, representing the initial operators on the dial. (The operator at index 0 is given but is not used in the decryption computation.)

The next \(q\) lines each contain an operation in one of the following formats:

• 1 pos d op — a modification operation that updates the sector at index pos (0-indexed) to have digit d (0-9) and operator op (either + or *).
• 2 pos — a query operation which uses the sector at index pos as the starting position for decryption.

outputFormat

For each query operation, output a single line with an integer representing the distance of the farthest zero interval from \(B_0\) as defined in the problem statement.

sample

6 4
1 2 3 4 5 6
+ * + * + *
2 0
1 3 9 +
2 4
2 2

5
1
3