4312. 「ROIR 2023 Day1」矩形分割

传统 $1000$ ms $512$ MiB
$1$ 通过 $1$ 提交

题目描述

译自 ROI Regional 2023 Day1 T1. Треугольная головоломка

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

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

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

输入格式

输入包含多组数据。第一行包含一个整数 $t$（$1 \leq t \leq 100$），表示输入数据组数。

接下来的每一行描述一组输入数据，包含四个整数 $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$），分别表示：

• $a$：矩形的高度（垂直方向的格子边界数，水平切割最多能切 $a-1$ 次）
• $b$：矩形的宽度（水平方向的格子边界数，垂直切割最多能切 $b-1$ 次）
• $k$：总切割次数
• $m$：最终需要分成的矩形数量

输出格式

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

样例

输入

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

输出

0 1
-1
2 3

样例说明

$1$. 第一组数据（$a=2, b=2, k=1, m=2$）：

$2$. 在第二组输入数据中，无法按要求进行切割。

$3$. 第三组数据（$a=3, b=5, k=5, m=12$）：

数据范围与提示

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