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

相应的答案定义为：

$(\texttt{ans}_{i,0},\texttt{ans}_{i,1}):=F_{i,r_i}(F_{i,r_i-1}(\dots F_{i,l_i}(x_i,0)\dots))$，

其中

若 $L_j\le X_i\le R_j$ 则 $F_{i,j}(x,y)=((a_jx+b_j)\bmod 2677114440,\max(b_j,y))$，

其余情况 $F_{i,j}(x,y)=(x,y)$。

你需要输出 $\texttt{ans}_{i,0}$ 与 $\texttt{ans}_{i,1}$ 的异或和。

输入格式

第一行两个整数 $n,m$。

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

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

输出格式

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

样例数据

样例输入

10 6
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

样例输出

3805
85
299
15769
204763
93

样例解释

在强制在线加密前，样例输入为：

10 6
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

子任务

Idea：nzhtl1477，Solution：ccz181078，Code：ccz181078，Data：ccz181078

对于 $100\%$ 的数据，满足：

$1\le n\le 10^6$

$1\le m\le 3\times 10^5$

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

$1\le L_i\le R_i\le n$

$1\le a_i\le 10^6$

$1\le b_i\le 10^6$

$1\le l_i\le r_i\le i$

$1\le X_i\le n$

$1\le x_i\le 10^6$。