You need to support $m$ operations. The $i$-th operation provides $L_i, R_i, a_i, b_i, l_i, r_i, X_i, x_i$.

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_j x + b_j) \bmod 2677114440, \max(b_j, y))$,

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

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

Input

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

The next $m$ lines each contain $L_i, R_i, a_i, b_i, l_i, r_i, X_i, x_i$, representing the $i$-th operation.

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

Output

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

Examples

Input 1

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

Output 1

3805
85
299
15769
204763
93

Note 1

Before applying the 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

Subtasks

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

Constraints

For $100\%$ of the data, it is satisfied that:

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