题目背景

题目描述

给定长度为 $n$ 的序列 $c_1,c_2,\cdots,c_n$，$c_i\in\{0,1\}$。序列中每个元素都对应一个括号，若 $c_i=0$ 则该位置上的括号是左括号，若 $c_i=1$ 则该位置上的括号是右括号。

我们用 $f(l,r)$ 表示区间 $[l,r]$ 内的括号序列是否合法。若 $c_l,c_{l+1},\cdots,c_r$ 组成的括号序列合法则为 $f(l,r)=1$，否则则为 $f(l,r)=0$。

合法括号序列的定义：

• 空串是合法括号序列；
• 若 A 是合法括号序列，(A) 是合法括号序列；
• 若 A 和 B 是合法括号序列，AB 是合法括号序列。

你需要在线地执行 $q$ 次操作，分为两种：

• 1 l r，查询 $\max\limits_{[l',r']\in[l,r]}\{(r'-l'+1)\cdot f(l',r')\}$，即查询 $[l,r]$ 间的最长合法括号子串的长度。
• 2 l r，对于 $i\in[l,r]$，将 $c_i$ 修改为 $(1-c_i)$，即将 $[l,r]$ 间的括号逐个调转方向。

输入格式

第一行两个正整数 $n,q$，分别代表序列长度和操作次数。

接下来 $n$ 个非负整数 $c_1,c_2\cdots,c_n$，代表初始序列。

接下来 $q$ 行，每行三个正整数 $op,l',r'$，表示操作类型和加密后的 $l,r$。

为了强制在线，数据经过加密，我们通过如下过程解密：记 $p$ 为上次查询操作的答案，没有则为 $0$。$l=((l'+p)\bmod n)+1,r=((r'+p)\bmod n)+1$，若 $l>r$ 则交换 $l,r$。

$op,l,r$ 表示操作的三个参数，若 $op=1$ 表示题面中的 1 l r 操作；若 $op=2$ 表示题面中的 2 l r 操作。

输出格式

对于每次查询，输出一行一个非负整数表示查询的答案。

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

提示

样例 1 解释

解密后的结果如下：

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

$7$ 次修改后的括号串为 $)((())()()$。

• 对于第一组询问，截取子串 $[3,6]$ 得 $(())$。整个子串是合法的括号序列，故答案为 $6-3+1=4$。
• 对于第二组询问，截取子串 $[6,9]$ 得 $)()($。子串 $[7,8]$ 是其中最长的合法括号子串，故答案为 $8-7+1=2$。
• 对于第三组询问，截取子串 $[10,10]$ 得 $)$。该子串中合法括号子串为空串，故答案为 $0$。

数据规模与约定

本题采用捆绑测试。

特殊性质：保证没有修改操作。

对于所有数据，$1 \le n\le 4 \times 10^6$，$1\le q \le 10^{5}$，$1 \le l',r' \le n$，$op\in\{1,2\}$，$c_i\in\{0,1\}$。

本题除 Subtask #3 外保证操作类型随机生成，即每次选择一个 $\{1,2\}$ 中的随机数（选到 $1$ 和 $2$ 的概率均为 $50\%$）作为 $op$。

本题题目附件附有大样例。