405808: GYM102114 G Glad You Came
Description
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.
![](https://espresso.codeforces.com/69549d64083192f41eb1a98b1966c2ec099405c2.png)
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
![](https://espresso.codeforces.com/2b78faaf0f982e817df422516ba8e4ebe299ff41.png)
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.
OutputFor each test case, output the answer in one line.
ExampleInput4Output
1 10 100 1000 10000
10 100 1000 10000 100000
100 1000 10000 100000 1000000
1000 10000 100000 1000000 10000000
1031463378Note
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.