蔡德仁的电脑里有 $n$ 个程序,每个程序的作用都是输入一个数,输出一个数。具体如下:
第 $i$ 个程序的输出是输入 $x$ 的函数 $f_i(x)$,具体地:
$$ f_i(x)= \begin{cases} (x-d_i)\bmod a_i & x\in [l_i,r_i] \\ x & x\notin [l_i,r_i]\\ \end{cases} $$
可以看出,程序由四个参数 $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}\gets f_i(\mathbf{v})$(每一步会调用一次程序 $i$ 来计算),最后电脑的校验码会是多少。
她有 $m$ 次询问,每次会分别给出 $x,L,R$,请你帮她计算。
询问是按强制在线顺序给出的,你必须得出前一次询问的答案才能知道下一次询问的参数。
输入格式
第一行两个数 $n,m$,分别表示程序个数和询问个数。
之后 $n$ 行,第 $i$ 行是四个数 $l_i,r_i,d_i,a_i$,含义如上述。
之后 $m$ 行,每行三个数 $L\oplus (z\bmod n),\;R\oplus (z\bmod n),\;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\%$ 的数据,满足 $1\le n,m\le 10^3$。
对于另外 $10\%$ 的数据,满足对每个函数都有 $d_i=0$。
对于另外 $10\%$ 的数据,满足对每次的询问都有 $L=1$ 且 $R=n$。
对于另外 $10\%$ 的数据,满足对每次的询问都有 $L=1$。
对于另外 $10\%$ 的数据,满足对每次的询问都有 $R=n$。
对于另外 $10\%$ 的数据,满足 $d_i,l_i,r_i,a_i,x\le 10^9$。
对于另外 $10\%$ 的数据,满足 $1\le n\le 3\times 10^4$,$1\le m\le 2\times 10^5$。
对于另外 $10\%$ 的数据,满足 $1\le n\le 5\times 10^4$,$1\le m\le 3\times 10^5$。
对于另外 $10\%$ 的数据,满足 $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 (z\bmod n),\;R\oplus (z\bmod n),\;x\oplus z$,其中 $z$ 是上次询问的答案(特别地,在第一次询问时,$z=0$),$\oplus$ 是按位异或。这个异或结果有可能超出 $L,R,z$ 本身的范围。数据范围内的 $L,R$ 范围指的是解除异或后实际询问的 $L,R$。
时间限制:$10\texttt{s}$
空间限制:$2\texttt{GB}$