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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:100  

Условие

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

Рассмотрим прямоугольное клетчатое поле размером 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 ≤ 109, 0 ≤ k ≤ 2 ⋅ 109, 1 ≤ m ≤ 1018, k < m

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

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

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
1 18 a = 1 первая ошибка
2 19 1 ≤ m ≤ 105 первая ошибка
3 20 1 ≤ k ≤ 105 2 первая ошибка
4 21 1 ≤ m ≤ 109 2 первая ошибка
5 22 нет 1 − 4 первая ошибка

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

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

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

    Иллюстрация к первому тесту:

    a = 2, b = 2, k = 1, m = 2.

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

    Иллюстрация к третьему тесту:

    a = 3, b = 5, k = 5, m = 12.

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

Стандартный вход Стандартный выход
1
3
2 2 1 2
1 2 2 3
3 5 5 12
0 1
-1
2 3

0.143s 0.028s 19