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 after all his operations are finished, where 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.
Let the i-th result value of calling the above function as fi (i = 1, 2, ..., 3m). The i-th operation of Steve is to update aj as vi if aj < vi (j = li, li + 1, ..., ri), where
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.
In the first sample, a = [1031463378] after all the operations.
In the second sample, a = [1036205629, 1064909195, 1044643689, 1062944339, 1062944339, 1062944339, 1062944339, 1057472915, 1057472915, 1030626924] after all the operations.
## Input
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.
## Output
For each test case, output the answer in one line.
[samples]
## Note
In the first sample, a = [1031463378] after all the operations.In the second sample, a = [1036205629, 1064909195, 1044643689, 1062944339, 1062944339, 1062944339, 1062944339, 1057472915, 1057472915, 1030626924] after all the operations.
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case:
- Let $ n \in \mathbb{Z} $ be the length of the array $ a = (a_1, \dots, a_n) $, initialized to all zeros.
- Let $ m \in \mathbb{Z} $ be the number of operations.
- Let $ X, Y, Z \in \mathbb{U}_{32} $ be initial 32-bit unsigned integers.
Define the RNG function:
$$
\text{rng}() := \left( X \leftarrow (X \oplus (X \ll 11)) \oplus (X \gg 8), \quad Y \leftarrow (Y \oplus (Y \gg 19)) \oplus (Y \ll 16), \quad Z \leftarrow (Z \oplus (Z \oplus (Z \ll 10)) \oplus (Z \gg 6)), \quad f_i = X \oplus Y \oplus Z \right)
$$
This function updates $ X, Y, Z $ and returns $ f_i $, the $ i $-th random value.
Let $ f_1, f_2, \dots, f_{3m} $ be the first $ 3m $ outputs of `rng()` in sequence.
For the $ i $-th operation ($ i \in \{1, \dots, m\} $):
- $ l_i = (f_{3i-2} \bmod n) + 1 $
- $ r_i = (f_{3i-1} \bmod n) + 1 $
- $ v_i = f_{3i} $
- If $ l_i > r_i $, swap $ l_i $ and $ r_i $.
- For each $ j \in \{l_i, l_i+1, \dots, r_i\} $, update:
$$
a_j \leftarrow \begin{cases}
v_i & \text{if } a_j < v_i \\
a_j & \text{otherwise}
\end{cases}
$$
**Constraints**
1. $ 1 \le T \le 100 $
2. $ 1 \le n \le 10^5 $, $ 1 \le m \le 5 \cdot 10^6 $
3. $ 0 \le X, Y, Z < 2^{30} $
4. $ \sum_{\text{test cases}} n \le 10^6 $
5. $ \sum_{\text{test cases}} m \le 5 \cdot 10^7 $
**Objective**
After all operations, compute:
$$
\bigoplus_{j=1}^{n} a_j
$$
where $ \oplus $ denotes bitwise XOR.