P15318 [VKOSHP 2025] System of Equations with XOR

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: $$xy = a \quad \text{and} \quad x \oplus y = b,$$ 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$.

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.

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.

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.