重（zhòng）庆的反重力系统终于研发成功了。小青鱼赶紧驱车前往卡纳维拉尔角，去看那巨大的反重力装置。

前往卡纳维拉尔角的的主公路可被视作一条数轴，数轴上等距排列着 $n$ 个收费站，标号为 $1\sim n$。有收费站这件事本身没什么问题，但问题是这里的收费站是由一群鸽子运营的。他们时而上班，时而下班，捉摸不透。

具体来说，初始时，所有收费站的运营时间均为 $[0,+\infty)$。鸽子们会随心情变化更改运营时间表，让某个收费站在某段时间停止运营，或者让某个收费站在某段时间恢复运营。

每个收费站都有一道闸门。从收费站 $i$ 的闸门后到达收费站 $i+1$ 的闸门前并不花费时间，并且你可以任意地在路上或某个收费站的闸门前后停留任意长的时间。但如果一个收费站不上班，那么你只能耐心等这个收费站上班之后才能通过该收费站（即从闸门前移动到闸门后）。

为了规划自己的路线，小青鱼需要一边关注收费站运营时间的变化，一边估算一些可能的行程的总时间花费。整个过程可以抽象为 $Q$ 次操作与询问：

1. 1 x l r：将收费站 $x$ 的时间区间 $[l,r+1)$ （即 $l \le t < r+1$）设置为正常运营。
2. 2 x l r：将收费站 $x$ 的时间区间 $[l,r+1)$ （即 $l \le t < r+1$）设置为停止运营。
3. 3 l r x：询问如果在时间 $x$ 从收费站 $l$ 的闸门后出发，到达收费站 $r$ 的闸门后的最早时间。

输入格式

第一行两个空格隔开的非负整数 $n,Q$。

接下来 $Q$ 行中，第 $i$ 行第一个数 $t_i$ 表示操作类型：

若 $t_i=1$，则接下来三个整数 $ x, l, r $，表示操作一，其中 $1 \le x \le n$。

若 $t_i=2$，则接下来三个整数 $ x, l, r $，表示操作二，其中 $1 \le x \le n$。

若 $t_i=3$，则接下来三个整数 $ l, r, x $，表示操作三，其中 $1\leq l\leq r\leq n$。

输出格式

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

样例一

input

3 3
2 2 0 1
2 3 1 2
3 1 3 0

output

3

explanation

第一次操作使得第二个收费站在 $[0,2)$ 不上班。

第二次操作使得第三个收费站在 $[1,3)$ 不上班。

此时如果在 $0$ 时刻出发从收费站 $1$ 出发走向收费站 $3$，最优策略是：

• 先在收费站 $1$ 的闸门后等到时刻 $2$，此时收费站 $2$ 开始上班；
• 在时刻 $2$ 通过收费站 $2$；
• 在收费站 $2$ 的闸门后等到时刻 $3$，此时收费站 $3$ 开始上班；
• 在时刻 $3$ 通过收费站 $3$。

注意出发点是在收费站 $1$ 的闸门后。也就是说，哪怕收费站 1 在 $[0, +\infty)$ 都不上班，也不影响该样例的输出。

样例二

input

6 10
2 3 0 2
3 1 2 4
3 1 4 2
2 4 3 5
2 2 2 4
3 3 5 4
3 3 4 3
3 4 5 3
3 1 1 5
3 1 3 2

output

4
3
6
6
3
5
5

数据范围

对于全部数据，保证 $1\leq n,Q\leq 2\cdot 10^5$。对于操作 1,2，$0\leq l\leq r \leq 10^9$。对于操作 3，$0\leq x \leq 10^9$。

时间限制：$\texttt{2s}$

空间限制：$1\texttt{GB}$