Background

Translated from ROIR 2023 D1T1。

Problem Description

There is a rectangle of size $a \times b$ made of unit grid cells. You need to split it into $m$ smaller rectangles using $k$ vertical or horizontal cuts. The smaller rectangles do not need to have the same size.

Each cut is not allowed to stop halfway: it must go from one side of the current rectangle to the opposite side. Cuts are only allowed along grid lines.

Input Format

The first line contains an integer $t$, the number of test cases.

The next $t$ lines each contain one test case. Each test case has four integers $a, b, k, m$, representing the rectangle size (length and width), the required number of cuts, and the required number of resulting smaller rectangles.

Output Format

For each test case, output in one line the number of horizontal cuts $h$ ($0 \le h < a$) and the number of vertical cuts $v$ ($0 \le v < b$) that can split the rectangle into $m$ smaller rectangles. If there are multiple ways, output the one with fewer horizontal cuts. If it is impossible to cut as required, output -1.

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

0 1
-1
2 3

Hint

This problem uses bundled testdata.

All testdata satisfy $1 \le t \le 100$, $1 \le a, b \le 10^9$, $0 \le k \le 2 \times 10^9$, $1 \le m \le 10^{18}$, and $k < m$.

Translated by ChatGPT 5