这是问题的困难版本。简单版本和困难版本之间的唯一区别是对 $$$a$$$、$$$b$$$、$$$c$$$ 和 $$$d$$$ 的约束。
给定 $$$4$$$ 正整数 $$$a$$$、$$$b$$$、$$$c$$$、$$$d$$$,其中 $$$a < c$$$ 且 $$$b < d$$$。查找任意满足以下条件的数字 $$$x$$$ 和 $$$y$$$ 对:
- $$$a < x \leq c$$$, $$$b < y \leq d$$$,
- $$$x \cdot y$$$ 可以被 $$$a \cdot b$$$ 整除。
请注意,所需的 $$$x$$$ 和 $$$y$$$ 可能不存在。
输入
输入的第一行包含一个整数 $$$t$$$ $$$(1 \leq t \leq 10$$$),即测试用例的数量。
测试用例的描述如下。
每个测试用例的唯一行包含四个整数 $$$a$$$、$$$b$$$、$$$c$$$ 和 $$$d$$$ ($$$1 \leq a < c \leq 10^9$$$、$$$1 \leq b < d \leq 10^9$$$)。
输出
对于每个测试用例,打印一对数字 $$$a < x \leq c$$$ 和 $$$b < y \leq d$$$,使得 $$$x \cdot y$$$ 可以被 $$$a \cdot b$$$ 整除。如果有多个答案,请打印其中任何一个。如果没有这样的数字对,则打印-1 -1。
示例
输入 #1
10 1 1 2 2 3 4 5 7 8 9 15 18 12 21 14 24 36 60 48 66 1024 729 373248 730 1024 729 373247 730 5040 40320 40319 1000000000 999999999 999999999 1000000000 1000000000 268435456 268435456 1000000000 1000000000
输出 #1
2 2 4 6 12 12 -1 -1 -1 -1 373248 730 -1 -1 15120 53760 -1 -1 536870912 536870912