Kera's line segment

题号：NC222898
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

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 $val_i$ .

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 \leq l_i \leq r_i \leq R$

输入描述:

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, val_i)$ 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 \leq n, m \leq 100000$ , $1\leq l_i \leq r_i \leq 3000$ , $0 \leq val_i \leq 1e9$ , $1\leq L \leq R \leq 3000$ .

输出描述:

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.

示例1

输入

复制

输出

复制

说明

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