Background

Problem Description

Given a sequence $c_1,c_2,\cdots,c_n$ of length $n$, where $c_i\in\{0,1\}$. Each element corresponds to a parenthesis: if $c_i=0$, the parenthesis at this position is a left parenthesis; if $c_i=1$, it is a right parenthesis.

Let $f(l,r)$ denote whether the parenthesis sequence in the interval $[l,r]$ is valid. If the sequence formed by $c_l,c_{l+1},\cdots,c_r$ is a valid parenthesis sequence, then $f(l,r)=1$; otherwise, $f(l,r)=0$.

Definition of a valid parenthesis sequence:

• The empty string is a valid parenthesis sequence.
• If A is a valid parenthesis sequence, then (A) is a valid parenthesis sequence.
• If A and B are valid parenthesis sequences, then AB is a valid parenthesis sequence.

You need to perform $q$ operations online, of two types:

• 1 l r: Query $\max\limits_{[l',r']\in[l,r]}\{(r'-l'+1)\cdot f(l',r')\}$, i.e., query the length of the longest valid parenthesis substring within $[l,r]$.
• 2 l r: For all $i\in[l,r]$, modify $c_i$ to $(1-c_i)$, i.e., flip every parenthesis in $[l,r]$ one by one.

Input Format

The first line contains two positive integers $n,q$, representing the sequence length and the number of operations.

The next line contains $n$ non-negative integers $c_1,c_2\cdots,c_n$, representing the initial sequence.

The next $q$ lines each contain three positive integers $op,l',r'$, representing the operation type and the encrypted $l,r$.

To enforce online processing, the data is encrypted and must be decrypted as follows: let $p$ be the answer to the previous query operation, or $0$ if there is none. Compute $l=((l'+p)\bmod n)+1$ and $r=((r'+p)\bmod n)+1$. If $l>r$, swap $l,r$.

Here, $op,l,r$ are the three parameters of the operation. If $op=1$, it means the 1 l r operation described above; if $op=2$, it means the 2 l r operation described above.

Output Format

For each query, output one line with a non-negative integer representing the answer.

10 10
0 1 1 0 0 1 0 0 1 1 
2 7 8
2 10 5
2 5 1
2 7 6
2 7 1
2 4 5
2 3 4
1 5 2
1 4 1
1 7 7

4
2
0

20 20
0 0 0 1 1 1 1 0 0 1 0 0 0 1 0 0 0 0 1 1 
2 16 7
2 12 10
1 4 5
1 14 7
1 16 7
2 15 12
1 12 2
1 3 4
1 1 10
2 14 3
2 19 1
1 20 9
2 14 16
1 10 13
1 6 8
2 1 2
1 8 16
1 9 15
1 17 12
2 15 14

0
2
8
2
0
2
6
4
0
2
0
0

Hint

Sample 1 Explanation

The decrypted result is as follows:

10 10
0 1 1 0 0 1 0 0 1 1 
2 8 9
2 1 6
2 2 6
2 7 8
2 2 8
2 5 6
2 4 5
1 3 6
1 6 9
1 10 10

After $7$ modifications, the parenthesis string becomes $)((())()()$.

• For the first query, take the substring $[3,6]$ to get $(())$. The whole substring is a valid parenthesis sequence, so the answer is $6-3+1=4$.
• For the second query, take the substring $[6,9]$ to get $)()($. The substring $[7,8]$ is the longest valid parenthesis substring within it, so the answer is $8-7+1=2$.
• For the third query, take the substring $[10,10]$ to get $)$. The valid parenthesis substring within this substring is the empty string, so the answer is $0$.

Constraints and Notes

This problem uses bundled testdata.

Special property: it is guaranteed that there are no modification operations.

For all testdata, $1 \le n\le 4 \times 10^6$, $1\le q \le 10^{5}$, $1 \le l',r' \le n$, $op\in\{1,2\}$, and $c_i\in\{0,1\}$.

For this problem, except for Subtask #3, it is guaranteed that the operation type is generated randomly, i.e., each time a random number from $\{1,2\}$ is chosen (with probability $50\%$ for both $1$ and $2$) as $op$.

A large sample is provided in the problem attachments.

Translated by ChatGPT 5