1178 : Kera’s line segment

Description

Kera likes line segments. He has n line segments, and each line segment can be described by l_i and r_i on the number axis. Moreover, each line segment Kera has its preferred value vali.

Then there are m operations:

• (op = 1, l_i , r_i , val_i) — Add a line segment(l_i , r_i , val_i) on the number axis, according to the above.

• (op = 2, L, R) — Query the maximum difference of preferred values of all line segments that are fully contained by the interval represented by [L, R].

In addition, a line segment(l_i , r_i , val_i) fully contained by the interval(L, R) means: L ≤ l_i≤ r_i ≤ R

Input

The first line contains two integer n and m.

Each of the next n lines contains 3 integers l_i, r_i and val_i.

Each of the next m lines contains 4 integers (op = 1, a_i , b_i , vali) or 3 integers (op = 2, A, B).

Specifically, in order to get the real input, you need to create a variable named LastAns with an initial value of 0.

For each operation(op = 1), l_i = a_i xor LastAns, r_i = b_i xor LastAns.

For each operation(op = 2), L = A xor LastAns, R = B xor LastAns, then LastAns updated to result of this query.

In addition, xor means binary exclusive OR. 1 ≤ n, m ≤ 100000, 1 ≤ l_i ≤ r_i ≤ 3000, 0 ≤ val_i ≤ 1e9, 1 ≤ L ≤ R ≤ 3000.

Output

For each operation(op = 2) , print an integer to represent the maximum difference of preferred values. It is guaranteed that each query fully contains at least one line segment.

Sample

3 5
2 3 1
5 6 4
4 10 5
2 2 5
2 2 6
2 2 9
1 2 3 20
2 5 14

0
3
4
19

Hint

The real sample input:

3 5

2 3 1

5 6 4

4 10 5

2 2 5

2 2 6

2 1 10

1 6 7 20

2 1 10

Source