405808: GYM102114 G Glad You Came

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 f_i (i = 1, 2, ..., 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, ..., r_i), 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 ≤ 10⁵, 1 ≤ m ≤ 5·10⁶, 0 ≤ X, Y, Z < 2³⁰.

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

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

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

1031463378
1446334207
351511856
47320301347

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.