有一个线段的多重集 $S$。多重集与集合的区别在于，多重集允许同一线段出现多次，而集合则不允许。

给定两个整数 $n$ 和 $t$。你需要对该多重集进行 $n$ 次以下类型的操作：

1. 将线段 $[l, r]$ 插入多重集 $S$。该线段被分配一个 $id$ —— 即之前未分配给任何其他线段的最小正整数。
2. 从多重集 $S$ 中删除分配编号为 $id$ 的线段。保证在删除时，多重集 $S$ 中存在分配编号为 $id$ 的线段。
3. 计算多重集 $S$ 中与给定线段 $[l, r]$ 至少有 $k$ 个公共整数点的线段数量。

如果 $l_i \le x \le r_i$ 且 $l_j \le x \le r_j$，则称整数点 $x$ 是线段 $[l_i, r_i]$ 和 $[l_j, r_j]$ 的公共点。

输入格式

第一行包含两个整数 $n$ 和 $t$ ($1 \le n \le 2 \cdot 10^5, 0 \le t \le 1$)，分别表示操作次数和常量。接下来的 $n$ 行描述了每个查询。

1. 第一类查询的格式为：1 ai bi ($0 \le a_i, b_i \le 2 \cdot 10^9$)。
2. 第二类查询的格式为：2 idi ($1 \le id_i \le n$)。
3. 第三类查询的格式为：3 ai bi ki ($0 \le a_i, b_i, k_i \le 2 \cdot 10^9$)。

请注意，第一类和第三类查询中线段 $[l_i, r_i]$ 的端点是加密的，为了解码它们，你需要执行以下变换：

$$l_i = (a_i \oplus (t * lastans)) \quad r_i = (b_i \oplus (t * lastans))$$

其中 $lastans$ 是上一次第三类查询的答案（初始时 $lastans$ 等于 0）。如果发现 $l_i$ 大于 $r_i$，则应交换 $l_i$ 和 $r_i$ 的值。

保证输入中至少有一个第三类查询。 这里 $\oplus$ 表示按位异或运算。 请注意，本题有不同寻常的内存限制。

输出格式

对于每个第三类查询，在单独的一行中输出答案。

子任务

本题包含六个子任务：

1. $n \le 5 \cdot 10^3$。得 7 分。
2. $n \le 10^5$。首先是第一类查询，然后是第三类查询，且没有第二类查询。得 15 分。
3. $n \le 2 \cdot 10^5$，$k_i = 1$ 对于所有第三类查询。得 16 分。
4. $n \le 10^5$，$t = 0$。得 17 分。
5. $n \le 10^5$。得 20 分。
6. $n \le 2 \cdot 10^5$。得 25 分。

样例

输入 1

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

输出 1

0
2
0

输入 2

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

输出 2

0
2