题目描述

有一个初始为空的线段集，你需要处理 $q$ 组询问，每组询问的格式为如下三种之一：

1. 加入一条新线段 $[l_i,r_i]$。
2. 将线段集里所有与 $[l_i,r_i]$ 相交的线段修改为其与 $[l_i,r_i]$ 的交。
3. 求出线段集里所有与 $[l_i,r_i]$ 相交的线段与 $[l_i,r_i]$ 的交的长度和。

两条线段 $[a,b],[c,d]$ 相交，当且仅当 $\max\{a,c\} \leq \min\{b,d\}$，它们的交为 $[\max\{a,c\},\min\{b,d\}]$。

一条线段 $[a,b]$ 的长度为 $b-a$。

在部分测试点中，你需要在线地进行这些操作。

注意：在本题中，线段可能退化为单点。

输入格式

第一行两个正整数 $q$ 和 $type$，分别表示操作次数和强制在线参数。

接下来 $q$ 行，每行三个正整数 $opt,l_i',r_i'$，其中 $opt$ 表示操作类型。

我们记 $last$ 表示上一次 $3$ 询问的答案（$last$ 初始为 $0$），则真实的 $l_i = ( l_i' + type \times last ) \bmod ( 2 \times 10^5 + 1 ), r_i = ( r_i' + type \times last ) \bmod ( 2 \times 10^5 + 1 )$。

数据保证 $1 \leq l_i \leq r_i \leq 2 \times 10^5$。

输出格式

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

9 0
1 1 5
1 6 8
1 2 3
3 3 8
2 4 6
1 5 9
2 2 7
3 2 7
3 3 6

4
4
2

提示

【样例解释】

每次操作后的线段集：

• 第一次后：$\{ [1,5] \}$
• 第二次后：$\{ [1,5],[6,8] \}$
• 第三次后：$\{ [1,5],[6,8],[2,3] \}$
• 第五次后：$\{ [4,5],[6,6],[2,3] \}$
• 第六次后：$\{ [4,5],[6,6],[2,3],[5,9] \}$
• 第七次后：$\{ [4,5],[6,6],[2,3],[5,7] \}$

【数据范围】

记 $k_1,k_2,k_3$ 分别为 $opt=1,2,3$ 的询问个数。

测试点编号	$k_1 \leq$	$k_2 \leq$	$k_3 \leq$	$type=$	特殊性质
$1 \sim 2$	$100$			$=0$	无
$3 \sim 5$	$10^5$	$5$	$3 \times 10^5$
$6 \sim 8$		$10^5$	$1$		所有 $2$ 操作在所有 $1$ 操作之后
$9 \sim 12$			$3 \times 10^5$
$13 \sim 17$					$l_i \leq 10^5 \leq r_i$
$18 \sim 20$	$5 \times 10^4$				无
$21 \sim 25$	$10^5$			$=1$

对于所有数据，$1 \leq q \leq 5 \times 10^5$, $k_3 \geq 1$, $0 \leq l_i',r_i' \leq 2 \times 10^5$, $1 \leq l_i \leq r_i \leq 2 \times 10^5$，$0 \leq type \leq1$，$1 \leq opt \leq 3$。