题目描述

爱丽丝和鲍勃喜欢涉及随机数的问题。一天，他们想出了以下问题：

• 首先，爱丽丝从 $1$ 到 $2^{31} - 1$ 的范围内随机选择一个整数 $x$，所有数字等概率出现。
• 然后，鲍勃从 $1$ 到 $2^{31} - 1$ 的范围内随机选择一个整数 $y$，所有数字等概率出现。
• 他们计算这两个数的乘积 $a = x \cdot y$ 以及它们的按位异或 $b = x \oplus y$。

现在给你两个结果整数 $a$ 和 $b$。请找出任意一对自然数 $x$ 和 $y$，使得：

其中 $\oplus$ 表示按位异或运算。

回忆一下，两个非负整数的按位“异或”（$\oplus$，xor）定义如下：将两个数写成二进制形式；结果的第 $i$ 个二进制位为 1 当且仅当两个参数中恰好有一个在该位为 1。例如，($14$ xor $7$) = ($1110_2 \oplus 0111_2$) = $1001_2$ = $9$。

输入格式

输入的第一行包含一个整数 $t$ （$1 \leq t \leq 200\,000$）—— 测试用例的数量。

接下来的 $t$ 行中，每行包含两个整数 $a$ 和 $b$ （$1 \leq a < 2^{62}$， $0 \leq b < 2^{31}$）—— 下一个测试用例的描述。

输出格式

对于每个测试用例，在单独的一行中输出两个由空格分隔的自然数 $x$ 和 $y$，使得 $xy = a$ 且 $x \oplus y = b$。

如果有多个有效答案，你可以输出任意一个。

本题不能输出文末换行。

2
21 4
9 0

7 3
3 3

提示

本题共有 $100$ 个测试，包括题目中的样例。保证在除样例外的所有测试中，$t = 200\,000$，且每个测试用例的 $a$ 和 $b$ 都是由爱丽丝和鲍勃随机选择 $x$ 和 $y$ 生成的。

翻译由 DeepSeek 完成