P 哥的桶

题目描述

P 哥现在有 $n$ 个桶，它们排成了一排，这些桶可以装下任意多个球。每个球有一个固定的价值。 P 哥时不时地会找新球，并把新找的球丢进某个桶里面。我们用 $1\;k\;x$ 来表示 P 哥找了一个价值为 $x$ 的球，并且丢进了 $k$ 号桶里面。 P 哥每次会在特定的桶里面拿出一些球。我们用 $2\;l\;r$ 来表示 P 哥在 $l$ 号桶到 $r$ 号桶之间拿球。P 哥希望拿出来的球的价值异或和尽可能大。 **注意：P 哥拿出这些球后会把它们物归原位。**

输入输出格式

输入格式


第一行两个整数 $n, m$，依次表示 P 哥的操作次数、这组数据会涉及到的最大编号。 接下来 $n$ 行，每行三个整数，表示操作。操作格式如题。

输出格式


对于每个 2 操作，输出 P 哥拿出的球的最大价值异或和。

输入输出样例

输入样例 #1

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

输出样例 #1

3
7

输入样例 #2

11 10
2 6 9
1 9 1523456696
1 1 1818963290
2 6 7
1 1 102229226
2 1 9
2 3 7
1 5 34895532
1 1 1652480680
1 1 1477666032
2 1 10

输出样例 #2

0
0
1818963290
0
1857442578

说明

对于 $20 \%$ 的数据，满足 $n,m\leq 100$。 对于 $40 \%$ 的数据，满足 $n,m\leq 1000$。 另有 $20 \%$ 的数据，所有询问满足 $l=1$，$r=m$。 对于 $100 \%$ 的数据，满足 $1 \le n, m \leq 5 \times 10^4$，$1 \le l\leq r\leq m$，$1 \le k \leq m$，$0 \le x \leq 2^{31}-1$。