#P1744E2. Divisible Numbers (hard version)
Divisible Numbers (hard version)
Description
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 < c$ and $b < d$. Find any pair of numbers $x$ and $y$ that satisfies the following conditions:
- $a < x \leq c$, $b < y \leq d$,
- $x \cdot y$ is divisible by $a \cdot b$.
Note that required $x$ and $y$ may not exist.
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 < c \leq 10^9$, $1 \leq b < d \leq 10^9$).
For each test case print a pair of numbers $a < x \leq c$ and $b < 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.
Input
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 < c \leq 10^9$, $1 \leq b < d \leq 10^9$).
Output
For each test case print a pair of numbers $a < x \leq c$ and $b < 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.
Samples
<div class="test-example-line test-example-line-even test-example-line-0">10</div><div class="test-example-line test-example-line-odd test-example-line-1">1 1 2 2</div><div class="test-example-line test-example-line-even test-example-line-2">3 4 5 7</div><div class="test-example-line test-example-line-odd test-example-line-3">8 9 15 18</div><div class="test-example-line test-example-line-even test-example-line-4">12 21 14 24</div><div class="test-example-line test-example-line-odd test-example-line-5">36 60 48 66</div><div class="test-example-line test-example-line-even test-example-line-6">1024 729 373248 730</div><div class="test-example-line test-example-line-odd test-example-line-7">1024 729 373247 730</div><div class="test-example-line test-example-line-even test-example-line-8">5040 40320 40319 1000000000</div><div class="test-example-line test-example-line-odd test-example-line-9">999999999 999999999 1000000000 1000000000</div><div class="test-example-line test-example-line-even test-example-line-10">268435456 268435456 1000000000 1000000000</div>
2 2
4 6
12 12
-1 -1
-1 -1
373248 730
-1 -1
15120 53760
-1 -1
536870912 536870912