시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 512 MB 3 3 3 100.000%

## 문제

Steve has an integer array $a$ of length $n$ (1-based). He assigned all the elements as zero at the beginning. After that, he made $m$ operations, each of which is to update an interval of a with some value. You need to figure out $\oplus_{i=1}^{n}{(i \cdot a_i)}$ after all his operations are finished, where $\oplus$ means the bitwise exclusive-OR operator.

In order to avoid huge input data, these operations are encrypted through some particular approach.

There are three unsigned 32-bit integers X, Y and Z which have initial values given by the input. A random number generator function is described as following, where ∧ means the bitwise exclusive-OR operator, << means the bitwise left shift operator and >> means the bitwise right shift operator. Note that function would change the values of X, Y and Z after calling.

 1: function RNG61()
2:     X ← X ∧ (X << 11)       ▷ 32-bit unsigned integer overflow might occur
3:     X ← X ∧ (X >> 4)
4:     X ← X ∧ (X << 5)        ▷ 32-bit unsigned integer overflow might occur
5:     X ← X ∧ (X >> 14)
6:     W ← X ∧ (Y ∧ Z)         ▷ as a partial 32-bit unsigned integer
7:     X ← Y
8:     Y ← Z
9:     Z ← W
10:     return Z
11: end function


Let the $i$-th result value of calling the above function as $f_i$ ($i = 1, 2, \dots , 3m$). The $i$-th operation of Steve is to update $a_j$ as $v_i$ if $a_j < v_i$ ($j = l_i, l_i + 1, \dots , r_i$), where

$\begin{cases} l_i = \min {((f_{3i-2} \mod{n}) + 1, (f_{3i-1} \mod{n}) + 1)} \\ r_i = \max {((f_{3i-2} \mod{n}) + 1, (f_{3i-1} \mod{n}) + 1)} ~ (i = 1, 2, \dots, m)\text{.} \\ v_i = f_{3i} \mod{2^{30}} \end{cases}$

## 입력

The first line contains one integer T, indicating the number of test cases.

Each of the following T lines describes a test case and contains five space-separated integers n, m, X, Y and Z.

1 ≤ T ≤ 100, 1 ≤ n ≤ 105, 1 ≤ m ≤ 5 · 106, 0 ≤ X, Y, Z < 230.

It is guaranteed that the sum of n in all the test cases does not exceed 106 and the sum of m in all the test cases does not exceed 5 · 107.

## 출력

For each test case, output the answer in one line.

## 예제 입력 1

4
1 10 100 1000 10000
10 100 1000 10000 100000
100 1000 10000 100000 1000000
1000 10000 100000 1000000 10000000


## 예제 출력 1

1031463378
1446334207
351511856
47320301347


## 힌트

In the first sample, a =  after all the operations.

In the second sample, a = [1036205629, 1064909195, 1044643689, 1062944339, 1062944339, 1062944339, 1062944339, 1057472915, 1057472915, 1030626924] after all the operations.