Cross Divine Name's Programs

There are $n$ programs in the computer of Cross Divine Name. Each program takes an integer as input and outputs an integer. The $i$-th program is defined by four parameters $l_i$, $r_i$, $d_i$, and $a_i$ (with $0 \le d_i \le l_i \le r_i$ and all values are integers). The function of the $i$-th program is given by:

$$ f_i(x)=\begin{cases} (x-d_i)\bmod a_i & \text{if } x\in [l_i,r_i]\\ x & \text{if } x\notin [l_i,r_i]\\ \end{cases} $$

Additionally, the computer maintains a checksum (an integer) which is initially $0$. When the $i$-th program is called with input $x$, if $x \in [l_i, r_i]$ and $x-d_i \ge a_i$ (i.e. both the subtraction and the modulo operation "take effect"), then the program updates the checksum by performing a bitwise XOR with $a_i$.

Now, you are given an initial value $x$ stored in a variable $\mathbf{v}$ and you reset the checksum to $0$. Then, for a given query with indices $L$ and $R$, you call the programs sequentially from $i = L$ to $R$. That is, for each $i$ from $L$ to $R$, update

$$\mathbf{v} \gets f_i(\mathbf{v}).$$

Your task is to report the final checksum after the sequence of operations.

Note: The queries are given in an online manner. That is, you must process each query sequentially (compute the answer for the previous query before reading the next one).

inputFormat

The first line contains two integers $n$ and $m$, representing the number of programs and the number of queries.

The next $n$ lines each contain four integers: $l_i$, $r_i$, $d_i$, and $a_i$, describing the $i$-th program. It is guaranteed that $0 \le d_i \le l_i \le r_i$ and $a_i > 0$.

Then $m$ lines follow. Each query is given by three integers: $x$, $L$, and $R$, where $x$ is the initial value of variable $\mathbf{v}$, and the programs from index $L$ to $R$ (inclusive) are executed sequentially.

outputFormat

For each query, output a single integer on a new line, which is the final checksum after processing the specified range of programs.

sample

3 2
1 10 1 2
2 20 2 3
5 15 1 4
5 1 3
10 2 3

2
3

</p>