write a go solution for 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<=c, b<y<=d,
- x*y is divisible by a*b.

Note that required x and y may not exist.

Input Format:
The first line of the input contains a single integer t (1<=t<=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<=qa<c<=q10^9, 1<=qb<d<=q10^9).

Output Format:
For each test case print a pair of numbers a<x<=c and b<y<=qd such that x*y is divisible by a*b. If there are multiple answers, print any of them. If there is no such pair of numbers, then print -1 -1.

Note:
None. Output only the code with no comments, explanation, or additional text.