Description

Alice and Bob love problems involving random numbers. One day they came up with the following problem:

• First, Alice chooses a random integer $x$ from the range of $1$ to $2^{31} - 1$, all numbers are equally likely.
• Then, Bob chooses a random integer $y$ from the range of $1$ to $2^{31} - 1$, all numbers are equally likely.
• They calculate the product of these numbers $a = x \cdot y$ and their bitwise XOR $b = x \oplus y$.

You are given two resulting integers $a$ and $b$. Find any pair of natural numbers $x$ and $y$ such that:

where $\oplus$ denotes the bitwise XOR operation.

Recall that the bitwise "exclusive or" ($\oplus$, xor) of two non-negative integers is defined as follows: write both numbers in binary representation; the $i$-th binary digit of the result is 1 if exactly one of the arguments has it equal to 1. For example, ($14$ xor $7$) = ($1110_2 \oplus 0111_2$) = $1001_2$ = $9$.

Input Format

The first line of the input contains a single integer $t$ $(1 \leq t \leq 200\,000)$ --- the number of test cases.

In the following $t$ lines of input, there are two integers $a$ and $b$ ($1 \leq a < 2^{62}$, $0 \leq b < 2^{31}$) --- the description of the next test case.

Output Format

For each test case, output in a separate line two natural numbers $x$ and $y$, separated by a space, such that $xy = a$ and $x \oplus y = b$.

If there are multiple valid answers, you may output any of them.

2
21 4
9 0

7 3
3 3

Hint

In this problem, there are $100$ tests, including the example from the statement. It is guaranteed that in all tests, except for the example from the statement, $t = 200\,000$, and the numbers $a$ and $b$ for each test case were generated by choosing random numbers $x$ and $y$ by Alice and Bob.