UVA11996 Jewel Magic

我是一个魔术师。我有一串珠宝，由祖母绿和珍珠组成。我可以在绳子上插入新的珠宝，或者取下旧的。我甚至可以反转字符串的连续部分。任何时候，如果你指着两颗宝石问我，从这两颗宝石开始的宝石串的最长公共前缀（LCP）的长度是多少，我可以立即回答你的问题。你能比我做得更好吗？ 形式化地说，你会得到一个由 $0$ 和 $1$ 的字符串。你将处理四种操作。 在以下描述中，$L$ 表示字符串的当前长度，宝石位置从左到右编号为 $1$ 到 $L$。 1. 操作 $1$ 形如 `1 p c`，代表在位置 $p$ 之后插入一个宝石 $c$（$0 \le p \le L$，$p = 0$ 表示插入在整个字符串之前）。$c = 0$ 代表这是祖母绿，$c = 1$ 代表这是珍珠。 2. 操作 $2$ 形如 `2 p`，代表取下 $p$ 位置的宝石（$1 \le p \le L$）。 3. 操作 $3$ 形如 `3 p1 p2`，代表把区间 $[p_1,p_2]$ 的宝石们翻转（$1 \le p_1 < p_2 \le L$）。 4. 操作 $4$ 形如 `4 p1 p2`，代表询问区间 $[p_1,L]$ 的珠宝串和区间 $[p_2,L]$ 的珠宝串的 LCP 长度（$1 \le p_1 < p_2 \le L$）。其中，LCP 指的是最长公共前缀。

**本题有多组测试数据。** 每组测试数据的第一行包含整数 $n$ 和 $m$（$1≤n, m≤2 \times 10^5$），其中 $n$ 为初始珍珠数，$m$ 为操作数。 下一行包含一个长度为 $n$ 的 $01$ 字符串。 接下来的 $m$ 行，每一行包含一个操作，格式如题目描述所述。 输入以文件结束符（EOF）结束。

对于每一个操作 $4$，输出一行表示答案。

#### 样例解释 原字符串为 $000100001100$。 进行 `1 0 1` 操作后字符串变为 $1000100001100$。 进行 `3 7 10` 操作后字符串变为 $1000101000100$。 进行 `2 9` 操作后字符串变为 $100010100100$。 数据范围：$1 \le n,m \le 2\times 10^5$。