EI 在 BJOI 前集训的时候听到了集合分块题，他非常弱（现在依然很弱），比别人的算法多一个 $\log$ ，他想到的解决方法只有将分块大小修改，从而把复杂度包在里面变成 $\Theta(n \sqrt{n\log n})$ ，而且见到一道修改过的题后，他又不会做了：

有 $n$ 个集合 $S_i$ ，初始为空，接下来进行 $q$ 组操作：

1. 将第 $l$ 个集合到第 $r$ 个集合插入一个元素 $x$ 即对 $l \le i \le r$，$S_i \leftarrow S_i \cup \{x\}$。

2. 询问第 $l$ 个集合到第 $r$ 个集合的交集大小，即 $$\left| \bigcap_{i = l}^r S_i \right|$$

输入格式

第一行输入整数 $n, q$

接下来输入 $q$ 行，每行第一个数 $op$ 为操作类型

对应的输入为 1 $l\ r\ x$ 或者 2 $l\ r$

输出格式

对于每个操作 2 即询问，输出一个整数且换行表示答案。

样例 1

input

3 4
1 1 2 2
1 2 3 1
2 1 2
2 2 2

output

1
2

解释

操作后的各个集合：$[\{2\},\{1,2\},\{1\}]$

所以对于第一个询问，$\{2\} \cap \{1, 2\} = \{2\}$

样例 2

input

2 3
1 1 1 1
1 2 2 1
2 1 2

output

1

限制与约定

$1\le n, q \le 3 \times 10^5$, $1\le x \le q$, $1 \le l \le r \le n$

Subtask 1 (12 pts.)，$1\le n, q \le 500$，插入的元素数量 $|S| \le 10^5$

Subtask 2 (18 pts.)，$1 \le n, q \le 5 \times 10^3$，插入的元素数量 $|S| \le 10^5$

Subtask 3 (20 pts.)，$1\le n, q \le 10^5$，插入的元素数量 $|S| \le 10^5$

Subtask 4 (28 pts.)，$1\le n, q \le 10^5$

Subtask 5 (22 pts.)，$1 \le n, q \le 3 \times 10^5$

Subtask $+\infty$ (0 pts.)，你需要统计对于该区间的每一个子区间的答案之和。

时间限制：$2\,\mathrm{s}$

空间限制：$512\,\mathrm{MB}$