Problem Description

P Bro now has $n$ buckets arranged in a row. These buckets can hold any number of balls. Each ball has a fixed value.

From time to time, P Bro finds a new ball and throws it into a bucket. We use $1\;k\;x$ to mean that P Bro found a ball with value $x$ and threw it into bucket $k$.

Each time, P Bro will take out some balls from a specific range of buckets. We use $2\;l\;r$ to mean that P Bro takes balls from buckets $l$ to $r$. P Bro wants the XOR sum of the values of the balls he takes out to be as large as possible.

Note: After taking out these balls, P Bro will put them back to their original places.

Input Format

The first line contains two integers $n, m$, which represent the number of operations P Bro performs, and the maximum index involved in this testdata, respectively.

The next $n$ lines each contain three integers describing an operation. The operation format is as described in the statement.

Output Format

For each operation of type 2, output the maximum possible XOR sum of the values of the balls P Bro takes out.

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

Hint

For $20\%$ of the data, $n, m \leq 100$.

For $40\%$ of the data, $n, m \leq 1000$.

For another $20\%$ of the data, all queries satisfy $l = 1$ and $r = m$.

For $100\%$ of the data, $1 \le n, m \leq 5 \times 10^4$, $1 \le l \leq r \leq m$, $1 \le k \leq m$, and $0 \le x \leq 2^{31}-1$.

Translated by ChatGPT 5