Description

You need to support $m$ operations. In the $i$-th operation, $L_i, R_i, a_i, b_i, l_i, r_i, X_i, x_i$ are given.

The corresponding answer is defined as:

$(\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))$.

Where:

If $L_j\le X_i\le R_j$, then $F_{i,j}(x,y)=((a_jx+b_j)\bmod 2677114440,\max(b_j,y))$.

Otherwise, $F_{i,j}(x,y)=(x,y)$.

You need to output the bitwise XOR of $\texttt{ans}_{i,0}$ and $\texttt{ans}_{i,1}$.

Input Format

The first line contains two integers $n, m$.

The next $m$ lines describe the operations. The $i$-th line contains $L_i, R_i, a_i, b_i, l_i, r_i, X_i, x_i$, representing the $i$-th operation.

This problem is mandatory online. For $2\le i\le m$, every number in the input of the $i$-th operation must be XORed with the answer of the $(i-1)$-th operation.

Output Format

Output $m$ lines, each containing one integer, representing the answer for each operation.

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

Hint

Idea: nzhtl1477, Solution: ccz181078, Code: ccz181078, Data: ccz181078.

Sample explanation:

Before the mandatory online encryption, the sample input is:

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

Constraints

For $100\%$ of the testdata, the following holds:

$1\le n\le 10^6$

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

For $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$。

Translated by ChatGPT 5