Задача D. Разделение прямоугольника ≡

Условие

Аня играет в новую настольную игру «Клетчатое королевство».

Рассмотрим прямоугольное клетчатое поле размером a × b.

Необходимо разделить его на m прямоугольников вертикальными или горизонтальными разрезами. Прямоугольники не обязательно должны получиться равными. Необходимо суммарно провести ровно k разрезов.

Каждый разрез представляет собой прямую линию от одного края поля до другого края поля. Разрезы разрешено делать только по границам клеток — линиям сетки.

Выведите, сколько провести горизонтальных (0 ≤ h < a) и сколько вертикальных (0 ≤ v < b) разрезов. Если поле можно разрезать несколькими способами, выведите тот, в котором горизонтальных разрезов меньше. Если поле нельзя разрезать требуемым образом, выведите  − 1.

Формат входных данных

В первой строке дано ровно одно целое число t — количество тестов.

В следующих t строках находится описание тестов: в i-й строке через пробел даны четыре целых числа: a, b, k, m — высота и ширина поля, количество разрезов и количество прямоугольников соответственно.

Формат выходных данных

Для каждого теста выведите через пробел ровно два целых числа h и v — количество горизонтальных и количество вертикальных разрезов, если прямоугольное клетчатое поле можно разрезать требуемым образом, в противном случае выведите число  − 1.

Ограничения

1 ≤ t ≤ 100

1 ≤ a, b ≤ 10⁹, 0 ≤ k ≤ 2 ⋅ 10⁹, 1 ≤ m ≤ 10¹⁸, k < m

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Пояснение к примеру

В приведенном примере содержится три теста:

1. В первом тесте поле можно разрезать, как показано на рисунке:

   

2. Во втором тесте поле нельзя разрезать требуемым образом.
3. В третьем тесте поле можно разрезать, как показано на рисунке:

   

Примеры тестов

3
2 2 1 2
1 2 2 3
3 5 5 12

0 1
-1
2 3