eolymp
bolt
Try our new interface for solving problems
Problems

XOR pairs

XOR pairs

Time limit 0.5 seconds
Memory limit 256 MiB

For given non-negative integers X, A, B consider all pairs of non-negative integers (a, b) such that a xor b = X, aA 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 data

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 data

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.

Examples

Input example #1
6 1 4 10
1
2
3
4
5
6
7
8
9
10
Output example #1
1 7
2 4
3 5
8 14
9 15
10 12
11 13
12 10
13 11
14 8