18563번 - 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 \(\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 ≤ 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.

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.