P哥的桶

题目背景

P哥在IOI取得了金牌,现在他开始找女朋友了!

题目描述

P哥现在有$n$个桶,他们排成了一排,这些桶可以装下任意多个女朋友。每个女朋友有一个固定的颜值 P哥时不时地会找新女朋友,并把新找的女朋友丢进某个桶里面。我们用$1\;k\;x$来表示P哥找了一个颜值为$x$的女朋友,并且丢进了$k$号桶里面 P哥每天晚上需要在特定的桶里面找一些女朋友观赏。我们用$2\;l\;r$来表示P哥在$l$号桶到$r$号桶之间找女朋友。P哥希望观赏的女朋友颜值异或和尽可能大。 **注意:P哥观赏完这些后会女朋友把它们物归原位**

输入输出格式

输入格式


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

输出格式


对于每个观赏操作,输出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%的数据,满足$n,m\leq 5*10^4\;\;\;l\leq r\leq m\;\;\;k\leq m\;\;\;x\leq 2^{31}-1$