CF1744E2.Divisible Numbers (hard version)

This is an hard version of the problem. The only difference between an easy and a hard version is the constraints on $a$, $b$, $c$ and $d$.

You are given $4$ positive integers $a$, $b$, $c$, $d$ with $a \lt c$ and $b \lt d$. Find any pair of numbers $x$ and $y$ that satisfies the following conditions:

• $a \lt x \leq c$, $b \lt y \leq d$,
• $x \cdot y$ is divisible by $a \cdot b$.

Note that required $x$ and $y$ may not exist.

这是一个该问题的困难版本。简单版本与困难版本的唯一区别在于对 $a$、$b$、$c$ 和 $d$ 的约束条件。

给定 $4$ 个正整数 $a$、$b$、$c$、$d$，满足 $a \lt c$ 且 $b \lt d$。请找出任意一对数 $x$ 和 $y$，使其满足以下条件：

• $a \lt x \leq c$，$b \lt y \leq d$，
• $x \cdot y$ 能被 $a \cdot b$ 整除。

注意：满足要求的 $x$ 和 $y$ 可能并不存在。

The first line of the input contains a single integer $t$ $(1 \leq t \leq 10$), the number of test cases.

The descriptions of the test cases follow.

The only line of each test case contains four integers $a$, $b$, $c$ and $d$ ($1 \leq a \lt c \leq 10^9$, $1 \leq b \lt d \leq 10^9$).

输入的第一行包含一个整数 $t$（$1 \leq t \leq 10$），表示测试用例的数量。

随后是各测试用例的描述。

每个测试用例仅有一行，包含四个整数 $a$、$b$、$c$ 和 $d$（$1 \leq a \lt c \leq 10^9$，$1 \leq b \lt d \leq 10^9$）。

For each test case print a pair of numbers $a \lt x \leq c$ and $b \lt y \leq d$ such that $x \cdot y$ is divisible by $a \cdot b$. If there are multiple answers, print any of them. If there is no such pair of numbers, then print -1 -1.

对每个测试用例，输出一对数 $a \lt x \leq c$ 和 $b \lt y \leq d$，使得 $x \cdot y$ 能被 $a \cdot b$ 整除。若存在多组解，输出任意一组即可。若不存在满足条件的数对，则输出 -1 -1。