MZL's xor

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Description

MZL loves xor very much.Now he gets an array A.The length of A is n.He wants to know the xor of all ($A_i$+$A_j$)($1\leq i,j \leq n$)
The xor of an array B is defined as $B_1$ xor $B_2$...xor $B_n$

Input

Multiple test cases, the first line contains an integer T(no more than 20), indicating the number of cases.
Each test case contains four integers:$n$,$m$,$z$,$l$
$A_1=0$,$A_i=(A_{i-1}*m+z)$ $mod$ $l$
$1\leq m,z,l \leq 5*10^5$,$n=5*10^5$

Output

For every test.print the answer.

Sample Input

2 3 5 5 7 6 8 8 9

Sample Output

14 16

Hint

wange2014

Source

2015 Multi-University Training Contest 5

提交代码