XOR pairs#2915

XOR pairs

0,5 Sekunden
256 Megabyte
Leicht

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 , , .

Eingabe

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}.

Ausgabe

For each given in the input, output two integers and such that the pair is the -th pair in the described sequence.

Beispiele

Beispiel 1

Loading
Loading