Glad You Came
Time limit4sMemory limit512 MB
Apply m range-max updates (a_j = max(a_j, v_i)) to a zero array, where each l, r, v comes from a fixed 32-bit RNG, then output the XOR of i*a_i.
- Level
Hard8 of 10
- Topics
- Segment tree, Implementation, Math, Bit manipulation
- Solved
- No attempts yet
Problem
Steve has an integer array (a) of length (n) (1-based). He set all elements to zero at the start. Then he performs (m) operations, each of which updates an interval of (a) with some value. Find (\oplus_{i=1}^{n}{(i \cdot a_i)}) after all his operations are finished, where (\oplus) is the bitwise exclusive-OR operator.
To keep the input small, the operations are encrypted by a particular method.
Three unsigned 32-bit integers X, Y, Z are given with their initial values as input. The random number generator is described below, where ∧ is the bitwise exclusive-OR operator, << is the bitwise left shift operator, and >> is the bitwise right shift operator. Calling the function changes the values of X, Y, and Z.
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 (f_i) be the (i)-th value returned by calling the function above ((i = 1, 2, \dots, 3m)). Steve's (i)-th operation sets (a_j) to (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}]
Input
The first line contains one integer T, the number of test cases.
Each of the following T lines describes one test case with 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.
The sum of n over all test cases is at most 106, and the sum of m over all test cases is at most 5 · 107.
Output
For each test case, print the answer on one line.
Hint
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.