English Problem Statement

蔡德仁的电脑里有 $n$ 个程序，每个程序的作用都是输入一个数，输出一个数。具体如下：

第 $i$ 个程序的输出是输入 $x$ 的函数 $f_i(x)$，具体地：

$$f_i(x)=\{\begin{array}{ll}(x-d_i)mod{a}_i& x\in [l_i,r_i]\\ x& x\notin [l_i,r_i]\end{array}$$

可以看出，程序由四个参数 $l_i,r_i,d_i,a_i$ 决定，保证 $0\le d_i\le l_i\le r_i$ 且都是整数。程序的输入和输出也都是非负整数。

电脑里有一个校验码，初始为 $0$。

第 $i$ 个程序被调用的时候，如果输入的 $x$ 满足 $x\in [l_i,r_i]$ 且 $x-d_i\ge a_i$，也就是减法和取模都“发生”了，则这个程序会给电脑里的校验码按位异或上这个程序的 $a_i$。

蔡德仁想要知道，如果她有一个初始值为 $x$ 的变量 $\mathbf{v}$，先把电脑的校验码置 $0$，然后依次对 $i=L,L+1,\dots ,R$ 执行 $\mathbf{v}\leftarrow f_i(\mathbf{v})$（每一步会调用一次程序 $i$ 来计算），最后电脑的校验码会是多少。

她有 $m$ 次询问，每次会分别给出 $x,L,R$，请你帮她计算。

询问是按强制在线顺序给出的，你必须得出前一次询问的答案才能知道下一次询问的参数。

输入格式

第一行两个数 $n,m$，分别表示程序个数和询问个数。

之后 $n$ 行，第 $i$ 行是四个数 $l_i,r_i,d_i,a_i$，含义如上述。

之后 $m$ 行，每行三个数 $L\oplus (zmodn),R\oplus (zmodn),x\oplus z$ 表示一次询问，其中 $z$ 是上次询问的答案（特别地，在第一次询问时，$z=0$），$\oplus$ 是按位异或。

输出格式

对每个询问，输出一行一个数表示答案。

样例1

input

10 10
2 2 2 2
1 2 0 1
1 1 0 1
0 0 0 1
2 2 0 1
3 3 0 1
22 22 18 14
5 5 1 4
1 1 0 1
1 1 0 1
2 10 73
3 9 70
1 9 71
1 5 71
1 10 8
1 10 67
1 10 5
5 14 93
3 10 14
3 10 88

output

0
0
0
0
0
0
4
0
0
0

样例2

input

20 20
1 1 0 1
18 23 8 11
5 9 4 4
1 2 1 1
37 38 18 19
3 3 2 1
14 18 5 9
1 1 0 1
2 3 2 1
2 2 1 1
1 1 0 1
1 1 1 1
3 3 1 1
1 1 0 1
15 15 8 7
1 1 0 1
1 1 0 1
1 2 1 1
1 2 1 1
33 65 3 32
1 15 18
1 20 79
1 19 8
13 16 39
4 24 56
2 20 75
4 10 1
8 13 40
2 20 87
1 20 93
1 2 69
2 19 84
1 20 35
15 30 4
10 16 70
2 20 1
1 16 57
2 20 54
14 31 50
6 20 53

output

0
0
4
32
0
0
0
0
0
0
0
0
32
0
0
0
0
32
0
32

样例3~7

见附件下载。

数据范围与提示

对于 $5\mathrm{\%}$ 的数据，满足 $1\le n,m\le {10}^3$。

对于另外 $10\mathrm{\%}$ 的数据，满足对每个函数都有 $d_i=0$。

对于另外 $10\mathrm{\%}$ 的数据，满足对每次的询问都有 $L=1$ 且 $R=n$。

对于另外 $10\mathrm{\%}$ 的数据，满足对每次的询问都有 $L=1$。

对于另外 $10\mathrm{\%}$ 的数据，满足对每次的询问都有 $R=n$。

对于另外 $10\mathrm{\%}$ 的数据，满足 $d_i,l_i,r_i,a_i,x\le {10}^9$。

对于另外 $10\mathrm{\%}$ 的数据，满足 $1\le n\le 3\times {10}^4$，$1\le m\le 2\times {10}^5$。

对于另外 $10\mathrm{\%}$ 的数据，满足 $1\le n\le 5\times {10}^4$，$1\le m\le 3\times {10}^5$。

对于另外 $10\mathrm{\%}$ 的数据，满足 $1\le n\le 7\times {10}^4$，$1\le m\le 4\times {10}^5$。

对于所有的数据，保证 $1\le n\le {10}^5$，$1\le m\le 5\times {10}^5$，$0\le d_i\le l_i\le r_i\le {10}^{18}$，$1\le x,a_i\le {10}^{18}$，$1\le L\le R\le n$。

注意输入的询问参数是 $L\oplus (zmodn),R\oplus (zmodn),x\oplus z$，其中 $z$ 是上次询问的答案（特别地，在第一次询问时，$z=0$），$\oplus$ 是按位异或。这个异或结果有可能超出 $L,R,z$ 本身的范围。数据范围内的 $L,R$ 范围指的是解除异或后实际询问的 $L,R$。

时间限制：$10\mathtt{\text{s}}$

空间限制：$2\mathtt{\text{GB}}$