CF1744E2 Divisible Numbers (hard version)

这是该问题的困难版本。简单版本与困难版本的唯一区别在于 $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$。

由 ChatGPT 4.1 翻译