A15372. 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 < 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.