E2. Делимые числа (сложная версия)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Единственное различие простой и сложной версии в ограничении на значения $$$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.

Пример
Входные данные
10
1 1 2 2
3 4 5 7
8 9 15 18
12 21 14 24
36 60 48 66
1024 729 373248 730
1024 729 373247 730
5040 40320 40319 1000000000
999999999 999999999 1000000000 1000000000
268435456 268435456 1000000000 1000000000
Выходные данные
2 2
4 6
12 12
-1 -1
-1 -1
373248 730
-1 -1
15120 53760
-1 -1
536870912 536870912