UOJ Logo Universal Online Judge

UOJ

附件下载 统计

English Problem Statement

蔡德仁的电脑里有 $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}$