题目描述

噔~噔~噔~噔~噔~噔~噔~噔~咚！

紧急通知，紧急通知！现在又有一架搭载了 1 道题的超脑航班即将抵达，其中有一位伪装成出题人的暗星人，他就是大家要做题的源头！

你需要支持 $m$ 次操作，第 $i$ 次操作给出 $L_i,R_i,a_i,b_i,l_i,r_i,X_i,x_i$。

相应的答案定义为：

$$(ans_{i,0},ans_{i,1}):=F_{i,r_i}(F_{i,r_i-1}(\ldots F_{i,l_i}(x_i,0)\ldots)) $$

其中

$$F_{i,j}(x,y)= \begin{cases} & ((a_jx+b_j)\mod 2677114440,\max(b_j,y)),&if\ L_j\leq X_i\leq R_j \\ & (x,y),&else \end{cases} $$

你需要输出 $ans_{i,0}$ 与 $ans_{i,1}$ 的异或和。

输入格式

第一行三个整数 $n,m,type$。

接下来 $m$ 行，第 $i$ 行为 $L_i,R_i,a_i,b_i,l_i,r_i,X_i,x_i$ 表示第 $i$ 次操作。

本题强制在线，若 $type=1$，则对 $2\leq i\leq m$，第 $i$ 次操作的输入的每个数需要与第 $i-1$ 次操作的答案异或。

输出格式

共 $m$ 行，每行一个整数，表示每个操作的答案。

样例 #1

样例输入 #1

10 6 1
3 5 93 89 1 1 3 39
3804 3800 3800 3791 3804 3807 3803 3720
83 93 90 121 87 86 81 110
298 291 302 383 298 296 303 266
15768 15760 15818 15836 15768 15773 15773 15822
204761 204753 204692 204781 204765 204765 204762 204678

样例输出 #1

3805
85
299
15769
204763
93

样例 #2

样例输入 #2

10 6 0
3 5 93 89 1 1 3 39
1 5 5 18 1 2 6 85
6 8 15 44 2 3 4 59
1 8 5 84 1 3 4 33
1 9 83 69 1 4 4 87
2 10 79 54 6 6 1 93

样例输出 #2

3805
85
299
15769
204763
93

提示

对于 $20\%$ 的数据，满足 $1\leq n,m\leq 1000$；

对于另外 $30\%$ 的数据，满足 $type=0$；

对于另外 $30\%$ 的数据，时限为 10s；

对于 $100\%$ 的数据，满足 $1\leq n\leq 10^6,1\leq m\leq 3\times 10^5$。

对于 $1\leq i\leq m$：

$1\leq L_i\leq R_i\leq n,1\leq a_i\leq 10^6,1\leq b_i\leq 10^6,1\leq l_i\leq r_i\leq i,1\leq X_i\leq n,1\leq x_i\leq 10^6,type\in\{0,1\}$。