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 M-2 elements after that, after the second operations M-4 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 non-negative 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/2-1 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$

----- Sample Input 1 ------ 
1
6 1 2
----- Sample Output 1 ------ 
4
----- explanation 1 ------ 
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 0-indexed 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.

Difficulty: VERY_HARD
Tags: Constructive algorithms

Ad-hoc

Starter code:

Solutions:
from sys import stdin
T = 1
T = int(stdin.readline())
for _ in range(T):
	(m, x, y) = map(int, stdin.readline().split())
	a = 1
	b = 2
	for i in range(2, int(m / 2 + 1)):
		mark = int(i * x / y)
		if a < mark + 1:
			a = 2 * a - 1
		elif a < i:
			a = 2 * a + 1
		elif a < mark + i:
			a = 2 * (a - i + 1)
		else:
			a = 2 * (a - i + 2)
		if b < mark + 1:
			b = 2 * b - 1
		elif b < i:
			b = 2 * b + 1
		elif b < mark + i:
			b = 2 * (b - i + 1)
		else:
			b = 2 * (b - i + 2)
	print(a ^ b)


def f(val, x, y, subsize):
	rem = int(subsize * (x / y))
	if val < rem:
		val = 2 * val
	elif val < subsize - 1:
		val = 2 * val + 2
	elif val < rem + subsize - 1:
		val = 2 * (val - (subsize - 1)) + 1
	else:
		val = 2 * (val - (subsize - 1)) + 3
	return val
for _ in range(int(input())):
	(m, x, y) = [int(i) for i in input().split()]
	a = 0
	b = 1
	for i in range(2, m // 2 + 1):
		a = f(a, x, y, i)
		b = f(b, x, y, i)
	print(a + 1 ^ b + 1)


T = int(input())
for _ in range(T):
	(M, X, Y) = [int(x) for x in input().split()]
	vPosition = 1
	wPosition = 2
	for arrayLength in range(2, M - 1, 2):
		evenT_Length = arrayLength // 2
		even_Length = arrayLength // 2 + 1
		odd_Length = arrayLength // 2 + 1
		positionGoing = even_Length * X // Y
		if vPosition < even_Length:
			new_vPosition = vPosition
			if new_vPosition > positionGoing:
				new_vPosition += 1
			new_vPosition = new_vPosition * 2 - 1
		else:
			new_vPosition = vPosition - evenT_Length
			if new_vPosition > positionGoing:
				new_vPosition += 1
			new_vPosition = new_vPosition * 2
		vPosition = new_vPosition
		if wPosition < even_Length:
			new_wPosition = wPosition
			if new_wPosition > positionGoing:
				new_wPosition += 1
			new_wPosition = new_wPosition * 2 - 1
		else:
			new_wPosition = wPosition - evenT_Length
			if new_wPosition > positionGoing:
				new_wPosition += 1
			new_wPosition = new_wPosition * 2
		wPosition = new_wPosition
	print(wPosition ^ vPosition)


def solve(M, X, Y):
	pos = [0, 1]
	l = 1
	while l < M // 2:
		pos = [2 * x if x < l else 2 * (x - l) + 1 for x in pos]
		l += 1
		rm = l * X // Y * 2
		pos = [x + 2 if x >= rm else x for x in pos]
	return pos[0] + 1 ^ pos[1] + 1
T = int(input())
for _ in range(T):
	(M, X, Y) = map(int, input().split())
	print(solve(M, X, Y))


def add(ind, half_cards, X, Y):
	cut = (half_cards + 1) * X // Y
	if ind < half_cards:
		if ind >= cut:
			return ind + 1
		else:
			return ind
	elif ind - half_cards >= cut:
		return ind + 2
	else:
		return ind + 1
T = int(input())
for case in range(T):
	(M, X, Y) = [int(val) for val in input().split()]
	cards = 2
	half_cards = 1
	ind1 = 0
	ind2 = 1
	while cards < M:
		ind1 = add(ind1, half_cards, X, Y)
		ind2 = add(ind2, half_cards, X, Y)
		cards += 2
		half_cards += 1
		if ind1 < half_cards:
			ind1 *= 2
		else:
			ind1 = (ind1 - half_cards) * 2 + 1
		if ind2 < half_cards:
			ind2 *= 2
		else:
			ind2 = (ind2 - half_cards) * 2 + 1
	print(ind1 + 1 ^ ind2 + 1)


def solve1(m, a, b):
	ret = [0, 1]
	for n in range(4, m + 2, 2):
		p = a * (n // 2) // b
		ret = [a if a < p else a + 1 if a < p + n // 2 - 1 else a + 2 for a in ret]
		ret = [2 * (a % (n // 2)) + (1 if a >= n // 2 else 0) for a in ret]
	return ret

def solve(m, a, b):
	(a, b) = solve1(m, a, b)
	return a + 1 ^ b + 1
import sys
f = sys.stdin
t = int(f.readline())
for i in range(t):
	(m, a, b) = map(int, f.readline().split())
	print(solve(m, a, b))