Comet OJ

C0989 [SHOI2015]脑洞治疗仪

内存限制：256 MB 时间限制：1000 ms

题目描述

曾经发明了自动刷题机的发明家 SHTSC 又公开了他的新发明：脑洞治疗仪——一种可以治疗他因为发明而日益增大的脑洞的神秘装置。

为了简单起见，我们将大脑视作一个 01 序列。$1$ 代表这个位置的脑组织正常工作，$0$ 代表这是一块脑洞。

0.PNG

脑洞治疗仪修补某一块脑洞的基本工作原理就是将另一块连续区域挖出，将其中正常工作的脑组织填补在这块脑洞中。（所以脑洞治疗仪是脑洞的治疗仪？）

例如，用上面第 $8$ 号位置到第 $10$ 号位置去修补第 $1$ 号位置到第 $4$ 号位置的脑洞，我们就会得到：

00.PNG

如果再用第 $1$ 号位置到第 $4$ 号位置去修补第 $8$ 号位置到第 $10$ 号位置：

000.PNG

这是因为脑洞治疗仪会把多余出来的脑组织直接扔掉。

如果再用第 $7$ 号位置到第 $10$ 号位置去填补第 $1$ 号位置到第 $6$ 号位置：

0000.PNG

这是因为如果新脑洞挖出来的脑组织不够多，脑洞治疗仪仅会尽量填补位置比较靠前的脑洞。

假定初始时 SHTSC 并没有脑洞，给出一些挖脑洞和脑洞治疗的操作序列，你需要即时回答 SHTSC 的问题：在大脑某个区间中最大的连续脑洞区域有多大。

输入格式

第一行两个整数 $n$、$m$，表示 SHTSC 的大脑可分为从 $1$ 到 $n$ 编号的 $n$ 个连续区域，有 $m$ 个操作。

以下 $m$ 行每行是下列三种格式之一：

  • $0 \quad l\quad r$：SHTSC 挖了一个范围为 $[l, r]$ 的脑洞。
  • $1\quad l_0 \quad r_0\quad l_1\quad r_1$：SHTSC 进行了一次脑洞治疗，用从 $l_0$ 到 $r_0$ 的脑组织修补 $l_1$ 到 $r_1$ 的脑洞。
  • $2\quad l \quad r$：SHTSC 询问 $[l, r]$ 区间内最大的脑洞有多大。

上述区间均在 $[1, n]$ 范围内。

输出

对于每个询问，输出一行一个整数，表示询问区间内最大连续脑洞区域有多大。

样例

样例输入 1

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

样例输出 1

3
3
6
6

提示

对于 $20\%$ 的数据，$n, m \leq 100$；

对于 $50\%$ 的数据，$n, m \leq 20000$；

对于 $100\%$ 的数据，$n, m \leq 200000$。