Ayesha loves numbers. One day she was reading about Fibonacci numbers, she was curious if instead of adding two preceding numbers to get the next number we take the xor of two preceding numbers, what would happen?
She selects a and b as the first and the second number of xor Fibonacci series respectively and the nth number of the series is given by:
F(N) = F(N – 1) ^ F(N – 2)
You are given Q queries and for each query, you are given a number d
1 ≤ d ≤ N, you have to find xor of all the elements from F(1) to F (N) excluding F(d).
INPUT
-
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
-
The first line of each test case contains three integers N, a, b.
-
The second line contains a single integer Q, the number of queries.
-
The following Q lines contains a single integer d.
OUTPUT
-
The output contains a single integer, xor of all the elements from F(1) to F (N) excluding F(d).
CONSTRAINTS
-
1 ≤ T ≤ 10.
-
2 ≤ N ≤ 109.
-
1 ≤ Q ≤ 105
-
0 ≤ a ≤ 105
-
0 ≤ b ≤ 105.
-
1 ≤ d ≤ N
Test case 1:
The elements of xor Fibonacci series are { 1 , 2 , 3 }.
For 1st query 2 xor 3 is 1.
For 2nd query 1 xor 3 is 2.
Test case 2:
The elements of xor Fibonacci series are { 2 , 3 , 1 , 2}.
For 1st query 3 xor 2 xor 1 is 0.
For 2nd query 2 xor 3 xor 2 is 3.
