题目描述

P 哥现在有 $n$ 个桶，它们排成了一排，这些桶可以装下任意多个球。每个球有一个固定的价值。

P 哥时不时地会找新球，并把新找的球丢进某个桶里面。我们用 $1\;k\;x$ 来表示 P 哥找了一个价值为 $x$ 的球，并且丢进了 $k$ 号桶里面。

P 哥每次会在特定的桶里面拿出一些球。我们用 $2\;l\;r$ 来表示 P 哥在 $l$ 号桶到 $r$ 号桶之间拿球。P 哥希望拿出来的球的价值异或和尽可能大。

注意：P 哥拿出这些球后会把它们物归原位。

输入格式

第一行两个整数 $n, m$，依次表示 P 哥的操作次数、这组数据会涉及到的最大编号。

接下来 $n$ 行，每行三个整数，表示操作。操作格式如题。

输出格式

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

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

3
7

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

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$。