Bobo 精通数据结构!他想维护一个线段的集合 $S$。初始时,$S$ 为空。他会依次进行 $q$ 次操作,操作有 $2$ 种。
- 类型 $1$:给出 $l, r$,向集合 $S$ 中插入线段 $[l, r]$.
- 类型 $2$:给出 $l, r$,询问满足 $[x, y] \in S$ 且 $x \leq l \leq r \leq y$ 的线段 $[x, y]$ 数量。
帮 Bobo 求出每次询问的答案。
输入格式
输入文件包含多组数据,请处理到文件结束。
每组数据的第一行包含 $2$ 个整数 $n$ 和 $q$. 其中 $n$ 表示操作中 $r$ 的最大值。
接下来 $q$ 行中的第 $i$ 行包含 $3$ 个整数 $t_i, l_i, r_i$,表示第 $i$ 个操作属于类型 $t_i$,对应的参数是 $l_i$ 和 $r_i$.
输出格式
对于每个类型 $2$ 的询问,输出 $1$ 个整数表示对应的数量。
样例输入
1 2 1 1 1 2 1 1 4 4 1 1 4 2 2 3 1 1 4 2 2 3
样例输出
1 1 2
数据范围
- $1 \leq n, q \leq 10^5$
- $t_i \in \{1, 2\}$
- $1 \leq l_i \leq r_i \leq n$
- 对于 $t_i = 2$ 的操作,$r_i - l_i \leq 2$ 成立。
- 数据组数不超过 $10$.