Migrated from Lutece 3132 silent wind bell

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tag：Hash、二分、平衡树

尽管以一副知晓生命意义的口吻高谈阔论

清醒过来 我与情报弱者之间不过半斤八两

为了向情强哥证明你不是情报弱者，你需要帮助他解决一个困扰他许久的问题。

情强哥有一个初始时长度为 $n$ 的01串 $S$ ，他会对 $S$ 进行 $m$ 次操作，每次操作格式如下（假设在进行每个操作之前， $S$ 的长度为 $L$ ）：

• 1 p c，在 $S$ 的第 $p$ 个字符后面插入一个新的字符 $c$ （ $0\le p\le L,c\in\{0,1\}$ ，当 $p=0$ 时表示在 $S$ 开头插入）。
• 2 p，删除 $S$ 中第 $p$ 个字符（ $1\le p\le L$ ）。
• 3 p q，将 $S$ 中 $[p,q]$ 区间内的字符翻转（ $1\le p\le q\le L$ )。
• 4 p q，求出后缀 $S_{p\sim L}$ 和后缀 $S_{q\sim L}$ 的LCP的长度（ $1\le p\le q\le L$ )。

为了帮助你更好地理解问题，这里是情强哥对于出现的一些名词的解释：

• 区间翻转：对长为 $n$ 的字符串 $S$ 的区间 $[l,r]$ 进行翻转，结果为 $S_1,\cdots,S_{l-1},S_r,S_{r-1},\cdots,S_{l+1},S_l,S_{r+1},\cdots,S_n$ 。
• LCP：即最长公共前缀，即字符串 $S$ 的两个（或多个）后缀共同拥有的最长的前缀子串。

Input

输入的第一行包括两个正整数 $n,m$ ，分别表示初始时01串的长度以及操作的数量。

第二行包括一个长为 $n$ 的01串 $S$ 。

接下来的 $m$ 行每行一个操作，格式与意义如题面所述。

Output

对于每个第四种类型的操作，输出一行一个正整数表示答案。

Samples

12 9
000100001100
1 0 1
4 2 6
3 7 10
4 1 7
2 9
4 3 11
4 1 9
4 1 7
4 2 3

3
6
2
0
3
2

Constraints

$1\le n,m\le 2\times 10^5$ ，其余限制均在题面中给出。

Note

• 在经过操作1 0 1后， $S=1000100001100$
• 在经过操作3 7 10后， $S=1000101000100$
• 在经过操作2 9后， $S=100010100100$

Resources

2024 UESTC ICPC Training for Data Structures