28395번 - Разделение прямоугольника 서브태스크다국어

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

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

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

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

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

В первой строке дано ровно одно целое число $t$ — количество тестов ($1 \le t \le 100$).

В следующих $t$ строках находится описание тестов: в $i$-й строке через пробел даны четыре целых числа: $a$, $b$, $k$, $m$ — высота и ширина поля, количество разрезов и количество прямоугольников соответственно ($1 \le a, b \le 10^9$, $0 \le k \le 2 \cdot 10^9$, $1 \le m \le 10^{18}$, $k < m$).

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

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

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

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

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

2) Во втором тесте поле нельзя разрезать требуемым образом.

3) В третьем тесте поле можно разрезать, как показано на рисунке:

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

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