Ира играет в настольную игру «Клетчатое Герцогство».

Рассмотрим прямоугольное клетчатое поле размером $a × 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.

Подзадачи