Alice 和 Bob 正在玩一个涉及两个区间 $$$[l_1, r_1]$$$ 和 $$$[l_2, r_2]$$$ 的游戏,分别受整数 $$$x_1$$$ 和 $$$x_2$$$ 约束。区间满足 $$$1 \le l_1 \le r_1 \le x_1$$$ 和 $$$1 \le l_2 \le r_2 \le x_2$$$。
游戏玩法如下。在一个回合中,玩家必须选择两个间隔之一(假设第 $$$i$$$ 个间隔 $$$[l_i, r_i]$$$)并执行 正好一个 以下操作:
- 将 $$$l_i$$$ 替换为严格较小的整数 $$$l'_i$$$,使得 $$$1 \le l'_i \lt l_i$$$。
- 将 $$$r_i$$$ 替换为严格更大的整数 $$$r'_i$$$,使得 $$$r_i \lt r'_i \le x_i$$$。
游戏设置分两步进行:
- 首先,Alice 选择 $$$l_1$$$ 和 $$$r_1$$$ 的值来确定第一个区间。它必须是 $$$[1, x_1]$$$ 内的有效区间。
- 然后,选择第二个区间 $$$[l_2, r_2]$$$ 均匀随机 来自 $$$[1, x_2]$$$ 内所有可能的有效间隔。
一旦选择了时间间隔,游戏就会开始 爱丽丝先移动.
假设 Alice 和 Bob 都处于最佳状态,Alice 希望选择初始区间 $$$[l_1, r_1]$$$ 来最大化她获胜的概率。你的任务就是找到这样一个区间。如果有多个最佳区间,则可以输出其中任意一个。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的唯一行包含两个整数 $$$x_1$$$ 和 $$$x_2$$$ ($$$1 \le x_1, x_2 \le 5 \cdot 10^5$$$) - 两个区间的上限。
保证所有测试用例的 $$$x_1$$$ 总和不超过 $$$5 \cdot 10^5$$$。
保证所有测试用例的 $$$x_2$$$ 总和不超过 $$$5 \cdot 10^5$$$。
输出
对于每个测试用例,输出两个整数 $$$l_1$$$ 和 $$$r_1$$$ ($$$1 \le l_1 \le r_1 \le x_1$$$) – Alice 选择的最佳间隔。
如果有多个最佳间隔,则可以输出其中任意一个。
示例
输入复制
61 11 102 12 220 64578185367 133524
输出复制
1 1 1 1 2 2 1 2 5 12 37381 52023
注意
对于第一个测试用例,Alice 被迫选择 $$$[1, 1]$$$,因为它是唯一有效的选项。
对于第三个测试用例,如果 Alice 选择 $$$[2, 2]$$$,她一定会赢(概率 $$$1$$$);她可以用 $$$1$$$ 替换 $$$l_1$$$,之后鲍勃就无法进行有效的移动。请注意,$$$[1, 1]$$$ 在这里也是有效的获胜答案。
对于第四个测试用例,如果 Alice 选择 $$$[1, 2]$$$,她的获胜概率为 $$$2/3$$$。相比之下,选择 $$$[1, 1]$$$ 或 $$$[2, 2]$$$ 的获胜概率仅为 $$$1/3$$$。