For given non-negative integers , , and , consider all pairs of non-negative integers such that a\ \mathrm{xor}\ b = X, a \geq A, and b \geq B. Here, denotes the bitwise XOR operation ("" in Pascal, "\textbf{\^{}}" in C/C++/Java). Sort these pairs in increasing order by , and for pairs with the same , in increasing order by .
You need to find the -th pair among these pairs. Numbering starts from . You will need to answer thousands of such queries for the given , , .
The first line contains four integers , , , and , the number of test cases. Each of the next lines contains a positive integer .
It is guaranteed that 0 \leq X, A, B \leq 10^{18}, 1 \leq T \leq 10000, and 1 \leq N \leq 10^{18}.
For each given in the input, output two integers and such that the pair is the -th pair in the described sequence.
Beispiel 1