XOR pairs
For given non-negative integers X, A, B consider all pairs of non-negative integers (a, b) such that a xor b = X, a ≥ A and b ≥ B. Here a xor b is the xor-operation ("xor" in Pascal, "ˆ" in C/C++/Java). Let’s sort these pairs by a in increasing order and pairs with equal value of a by b in increasing order.
You need to find N-th pair among these pairs. Numeration starts from 1. But be ready to answer for thousands of such question for given X, A, B.
Input
The first line contains four integers X, A, B and T, the number of test cases. Each of the next T lines contains a positive integer N. It is guaranteed that 0 ≤ X, A, B ≤ 10^18, 1 ≤ T ≤ 10000 and 1 ≤ N ≤ 10^18.
Output
For each value of N in the input file output two space separated integers a and b, such that pair (a, b) is N-th pair among described sequence of pairs.