You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

安雅正在玩一款新的桌面游戏「格子王国」。我们来看一个大小为 $a \times b$ 的矩形格子。需要通过垂直或水平切割将其分成 $m$ 个矩形。矩形不一定要相等，总共需要进行 $k$ 次切割。

每次切割都是从矩形的一边到另一边的直线。切割只能沿着格子的边界线进行。

输出需要进行的水平切割次数 $h$ $(0 \leq h < a)$ 和垂直切割次数 $v$ $(0 \leq v < b)$。如果有多种切割方式，输出水平切割次数最少的那种。如果无法按要求切割矩形，输出 $-1$。

输入格式

输入包含多组数据。第一行包含一个整数 $t$ $(1 \le t \le 100)$，表示输入数据组数。

接下来的每一行描述了一组输入数据。第 $i$ 行包含四个整数 $a, b, k, m$ $(1 \leq a, b \leq 10^9, 0 \leq k \leq 2 \cdot 10^9, 1 \leq m \leq 10^{18}, k < m)$，分别表示矩形的高度和宽度、切割次数和矩形数量。

输出格式

对于每个测试，输出两个整数 $h$ 和 $v$，分别表示水平切割次数和垂直切割次数。如果无法按要求切割矩形，输出 $-1$。

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

0 1
-1
2 3

在样例中包含三组输入数据：

• 在第一组输入数据中，可以按图所示进行切割：

• 在第二组输入数据中，无法按要求进行切割。
• 在第三组输入数据中，可以按图所示进行切割：

数据范围与提示

详细子任务附加限制及分值如下表所示。