F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Glad You Came

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 3406    Accepted Submission(s): 1467


Problem 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 $\bigoplus_{i = 1}^{n}{(i \cdot a_i)}$ after all his operations are finished, where $\bigoplus$ 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 $\wedge$ 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, \cdots, 3 m)$. 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, \cdots, r_i)$, where
$$\begin{cases} l_i &= \min\left((f_{3 i - 2} \bmod n) + 1, (f_{3 i - 1} \bmod n) + 1\right) \\ r_i &= \max\left((f_{3 i - 2} \bmod n) + 1, (f_{3 i - 1} \bmod n) + 1\right) \\ v_i &= f_{3 i} \bmod 2^{30}\end{cases} (i = 1, 2, \cdots, m).$$
 

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 \leq T \leq 100$, $1 \leq n \leq 10^5$, $1 \leq m \leq 5 \cdot 10^6$, $0 \leq X, Y, Z < 2^{30}$.
It is guaranteed that the sum of $n$ in all the test cases does not exceed $10^6$ and the sum of $m$ in all the test cases does not exceed $5 \cdot 10^7$.
 

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

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

Sample Output
1031463378 1446334207 351511856 47320301347
 

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.
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-12-11 19:57:52, Gzip enabled