Это сложная версия задачи. Единственное различие простой и сложной версии в ограничении на значения \(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\) могут не существовать.
Выходные данные
Для каждого набора входных данных выведите пару чисел \(a < x \leq c\) и \(b < y \leq d\), для которой \(x \cdot y\) делится на \(a \cdot b\). Если есть несколько вариантов ответа, то выведите любой из них. Если такой пары чисел не существует, то выведите -1 -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
|