测试数据来自 system/2027

描述

佳佳是一名出色的魔术师，现在他有一个初始长度为 \(n\) 的 \(01\) 字符串。他会对这个字符串进行一些操作和询问。

假设当前字符串的长度为 \(L\)，则有以下三种操作。

操作一、用 1 p c 来标记，其中 \(0\le p\le L\)且\(c\)是\(0\)或\(1\)，表示在当前字符串第\(p\)个字符的后面插入一个新的字符 \(c\)；如果\(p=0\)表示在整个字符串的开头插入\(c\)。得到的新字符长度为比之前大一。

操作二、用 2 p 来标记，其中 \(1\le p\le L\)，表示删除当前的第\(p\)个字符，删除操作结束后，后面的字符会自动向前补齐，对应的新字符串长度会比之前小一。

操作三、用 3 s t 来表示，其中 \(1\le s\le t\le L\)，表示将字符串中第\(s\)个字符到第\(t\)个字符的一段整体翻转。反转后新的字符串长度不变。

佳佳还需要支持一种关于当前字符串的询问，用 4 s t 来表示，其中\(1\le s\le t\le L\)，考虑从第\(s\)个到最后一个字符形成的子串，与从第\(t\)个到最后一个字符形成的字串，询问他们两个字符串的最长公共前缀长度。

格式

输入格式

输入的第一行是两个整数 \(n\) 和 \(m\)，\(n\)是初始的字符串长度，\(m\)是总的操作和询问的次数。

第二行输入一个长度为\(n\)的 \(01\)字符串。

之后\(m\)行，每行给出一个操作或一个询问。

输出格式

对于每一次询问，输出一个正整数，表示最长公共前缀的长度。

样例1

样例输入1

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

样例输出1

3
6
2
0
3
2

限制

对于 \(30\%\) 的数据，\(n,m\le 5000\)。

对于 \(60\%\) 的数据，\(n,m\le 300000\)。

对于 \(100\%\) 的数据，\(n,m\le 500000\)。

前三组数据的时限每一组为 \(1\) 秒，后面每一组数据的时限为 \(10\) 秒。