Clarke is a patient with multiple personality disorder. One day, Clarke split into $n$ guys, named $1$ to $n$.
They will play a game called Lose Weight. Each of Clarkes has a weight $a[i]$. They have a baton which is always in the hand of who has the largest weight(if there are more than 2 guys have the same weight, choose the one who has the smaller order). The one who holds the baton needs to lose weight. i.e. $a[i]$ decreased by 1, where $i$ is the guy who holds the baton.
Now, Clarkes know the baton will be passed $q$ times. They want to know each one's weight after finishing this game.
Input
The first line contains an integer $T(1 \le T \le 10)$, the number of the test cases.
Each test case contains three integers $n, q, seed(1 \le n, q \le 10000000, \sum n \le 20000000, 1 \le seed \le 10^9+6)$, $seed$ denotes the random seed.
$a[i]$ generated by the following code.
long long seed;
int rand(int l, int r) {
static long long mo=1e9+7, g=78125;
return l+((seed*=g)%=mo)%(r-l+1);
}
int sum=rand(q, 10000000);
for(int i=1; i<=n; i++) {
a[i]=rand(0, sum/(n-i+1));
sum-=a[i];
}
a[rand(1, n)]+=sum;
Output
Each test case print a line with a number which is $(b[1]+1) xor (b[2]+2) xor ... xor (b[n]+n)$, where $b[i]$ is the $ith$ Clarke's weight after finishing the game.
Sample Input
1
3 2 1
Sample Output
20303
Hint:
At first, $a[1]=20701, a[2]=31075, a[3]=26351$.
At the first time, $a[2]$ decrease by 1.
At the second time, $a[2]$ decrease by 1.
Finally, $a[1]=20701, a[2]=31073, a[3]=26351$. So answer is $(20701+1)xor(31073+2)xor(26351+3)=20303$.
