Maximum XOR Sum in Buckets

There are \(n\) buckets arranged in a line. Each bucket can hold an arbitrary number of balls, and each ball has a fixed value. Initially, all buckets are empty. P performs the following two types of operations:

• Operation 1: "1 k x" — a ball with value \(x\) is added to bucket \(k\).
• Operation 2: "2 l r" — for all buckets from \(l\) to \(r\) (inclusive), select any subset of balls (each ball can be used at most once) such that the XOR sum of their values is maximized. Note: after the query, the balls are returned to their original buckets.

Your task is to process \(q\) operations and for each query (Operation 2) output the maximum XOR sum obtainable from the balls in the specified buckets.

inputFormat

The first line contains two space-separated integers \(n\) and \(q\), representing the number of buckets and the number of operations respectively.

The next \(q\) lines each contain an operation in one of the following two formats:

• "1 k x": add a ball with value \(x\) to bucket \(k\).
• "2 l r": query the maximum XOR sum that can be obtained by selecting a subset of balls from buckets \(l\) to \(r\) (inclusive).

outputFormat

For each query of type 2, output a single line containing the maximum XOR sum achievable from the selected buckets.

sample

5 5
1 2 3
1 3 5
2 2 3
1 5 10
2 1 5

6
15