J. Bit Lobon
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given two integers $$$L$$$ and $$$R$$$, your task is to compute the following three values:

  • $$$A$$$: the bitwise AND of all integers from $$$L$$$ to $$$R$$$ inclusive.
  • $$$O$$$: the bitwise OR of all integers from $$$L$$$ to $$$R$$$ inclusive.
  • $$$X$$$: the bitwise XOR of all integers from $$$L$$$ to $$$R$$$ inclusive.

Formally, you need to compute: $$$$$$ A = L\ \&\ (L+1)\ \&\ (L+2)\ \&\ \dots\ \&\ R $$$$$$ $$$$$$ O = L\ |\ (L+1)\ |\ (L+2)\ |\ \dots\ |\ R $$$$$$ $$$$$$ X = L\ \oplus\ (L+1)\ \oplus\ (L+2)\ \oplus\ \dots\ \oplus\ R $$$$$$

Bitwise operations work on the binary representation of integers, operating on bits of the same positions of the numbers involved.

  • & denotes the bitwise AND operation — the result has a $$$1$$$ only in bit positions where both numbers have a $$$1$$$. For example: $$$ 6 = 0110_2,\ 10 = 1010_2,\ 6\ \&\ 10 = 0010_2 = 2 $$$

  • | denotes the bitwise OR operation — the result has a $$$1$$$ in bit positions where at least one number has a $$$1$$$. For example: $$$ 6 = 0110_2,\ 10 = 1010_2,\ 6\ | \ 10 = 1110_2 = 14 $$$

  • $$$\oplus$$$ denotes the bitwise XOR operation — the result has a $$$1$$$ in bit positions where the bits of the two numbers are different. For example: $$$ 6 = 0110_2,\ 10 = 1010_2,\ 6\ \oplus\ 10 = 1100_2 = 12 $$$
Input

The first line of the input contains a single integer $$$t$$$ $$$(1 \leq t \leq 2 \times 10^5)$$$ — the number of test cases. Then $$$t$$$ test cases follow.

Each test case consists of a single line containing two space-separated integers, $$$L$$$ and $$$R$$$ $$$(0 \leq L \leq R \leq 10^{18})$$$ — the boundaries of the range (inclusive).

Output

For each test case, output three integers $$$A$$$, $$$O$$$, and $$$X$$$ in a line — the bitwise AND, OR, and XOR of all integers from $$$L$$$ to $$$R$$$ inclusive, in order.

Example
Input
5
8 12
0 5
1 10
16 32
100000000000 100000000000
Output
8 15 12
0 7 1
0 15 11
0 63 32
100000000000 100000000000 100000000000
Note

The calculations of the first test case:

$$$$$$ \begin{array}{rcl} 8 & = & 1000_2 \\ 9 & = & 1001_2 \\ 10 & = & 1010_2 \\ 11 & = & 1011_2 \\ 12 & = & 1100_2 \\ \hline A & = & 1000_2 \\ O & = & 1111_2 \\ X & = & 1100_2 \\ \end{array} $$$$$$