Shuffling

All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
Chef simulating the next process, imagine that we have an array A = {1, 2, ..., M}. Split it into two arrays with equal size with odd and even indexes from it. After that let's erase in each array numbers on the place [S*X/Y], where S denoting the size of array and merge these arrays(the first element of the second array will be after the last element of the first array), after the first operation A will contain exactly M2 elements after that, after the second operations M4 and so on. Chef making this procedure until A has more than 2 elements. In the end he wants to know the value of bitwise XOR elements that remain. He needs your help!
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains three nonnegative integers M, X and Y.
Output

Output in a single line the value of bitwise XOR of two elements that remain in the array A after M/21 operations split/merge as described above.
Constraints
 1 ≤ T ≤ 1000
 1 ≤ M ≤ 10^{6}
 M is even
 0 ≤ X < Y ≤ 10^{6}
 Sum of M over all test cases ≤ 5*10^{6}
Subtasks
 Subtask #1: (30 points) Sum of M over all test cases ≤ 10^{4}
 Subtask #2: (10 points) X = 0
 Subtask #3: (60 points) Original constraints
Example
Input: 1 6 1 2 Output: 4
Explanation
Example case 1. Initially we have A = {1, 2, 3, 4, 5, 6}. After splitting in two arrays we will have A' = {1, 3, 5} and B' = {2, 4, 6}. Let's erase from 0indexed A' and B' elements with index = [3*1/2]=1(3 and 4 respectively). After that merge A' and B' > A = {1, 5, 2, 6}, split A once again in A' = {1, 2} and B' = {5, 6} and erase elements with index = [2*1/2]=1(2 and 6 respectively), merge arrays A' and B' > A = {1, 5}. Answer is bitwise XOR of 1 and 5 = 4.
Author:  mgch 
Tester:  alex_2oo8 
Editorial  https://discuss.codechef.com/problems/SHUFFL 
Tags  easymedium, ltime54, mgch 
Date Added:  20112017 
Time Limit:  0.5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 