题目描述

给出 $n$ 个区间，一开始第 $i$ 个区间位于 $[L_i,R_i]$。

$m$ 次操作：

• 1 l r k：对于 $i\in[l,r]$，记修改前的第 $k$ 个区间为 $[L'_k,R'_k]$，执行 $[L_i,R_i]\leftarrow [L'_k,L'_k+R_i-L_i]$。
• 2 l r k：对于 $i\in[l,r]$，记修改前的第 $k$ 个区间为 $[L'_k,R'_k]$，执行 $[L_i,R_i]\leftarrow [R'_k-R_i+L_i,R'_k]$。
• 3 l r x：查询 $\sum\limits_{i=l}^r\left[x+\dfrac{1}{2}\in [L_i,R_i]\right]$。

输入格式

第一行两个正整数 $n, m$。

接下来 $n$ 行每行两个非负整数 $L_i,R_i$。

接下来 $m$ 行每行四个非负整数，表示一个操作。

输出格式

若干行，每行一个非负整数，表示答案。

10 10
1 6
16 18
9 10
17 20
6 18
6 19
14 18
2 9
8 18
2 15
2 1 2 5
2 6 6 5
3 1 5 11
3 9 10 12
3 4 7 20
1 1 7 1
3 8 9 12
2 1 1 2
1 4 6 8
3 3 5 3

1
2
0
1
2

提示

对于 $100\%$ 的数据，保证 $1\le n,m\le 2\times 10^5$，$0\le L_i\le R_i\le 10^9$，$1\le l\le r\le n$，$0\le x\le 10^9$，$1\le k\le n$。