这道题的核心是通过建立切割次数与矩形数量的数学关系，结合边界约束，求解水平切割次数$h$和垂直切割次数$v$。关键在于先推导公式，再枚举可能的$h$值验证合法性，最终找到最优解。

一、核心公式与约束条件

首先明确两个核心关系，这是解题的基础：

1. 矩形数量公式：水平切割$h$次会将矩形分成$h+1$行，垂直切割$v$次会分成$v+1$列，因此总矩形数为 $(h+1) \times (v+1) = m$。
2. 总切割次数公式：总切割次数为水平与垂直切割次数之和，即 $h + v = k$。

同时需满足以下边界约束（切割次数不能超过最大可能值）：

• 水平切割上限：$h \leq a-1$（矩形高度为$a$，最多有$a-1$条水平切割线）。
• 垂直切割上限：$v \leq b-1$（矩形宽度为$b$，最多有$b-1$条垂直切割线）。
• 非负约束：$h \geq 0$，$v \geq 0$。

二、解题步骤

基于上述公式，可通过“枚举$h$的可能值→计算$v$→验证所有约束”的流程求解，具体步骤如下：

1. 公式变形：由$h + v = k$得$v = k - h$，代入矩形数量公式得 $(h+1) \times (k - h + 1) = m$。我们需要找到满足该等式且符合所有约束的$h$。
2. 确定$h$的枚举范围：
   • 由$v = k - h \geq 0$得$h \leq k$。
   • 由$h \geq 0$和$h \leq a-1$得$h$的下限为$0$，上限为$\min(a-1, k)$。
   • 此外，$(h+1)$必须是$m$的约数（否则$(k - h + 1) = m/(h+1)$不是整数，无法满足矩形数量公式），因此只需枚举$m$的所有约数$d$，令$h = d - 1$，再验证$h$是否在上述范围内。
3. 验证约束：对每个枚举的$h$，计算$v = k - h$，检查：
   • $(h+1) \times (v+1) = m$（确保矩形数量正确）。
   • $v \leq b-1$且$v \geq 0$（垂直切割次数合法）。
4. 选择最优解：若存在多个合法的$h$，选择最小的$h$（题目要求“水平切割次数最少”）；若无合法解，输出$-1$。

三、关键优化：枚举$m$的约数

由于$m$可能极大（最大$10^{18}$），直接枚举$h$的所有可能值会超时，因此需通过“枚举$m$的约数”减少计算量：

• 约数的性质：若$d$是$m$的约数，则$m/d$也是$m$的约数，因此只需枚举到$\sqrt{m}$即可，时间复杂度为$O(\sqrt{m})$，对于$10^{18}$而言，$\sqrt{m}$最大为$10^9$，但结合$h$的范围限制（$h \leq \min(a-1, k)$），实际枚举量会大幅减少。

四、实现代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve() {
    ll a, b, k, m;
    cin >> a >> b >> k >> m;
    
    vector<pair<ll, ll>> candidates;  // 存储合法的(h, v)对
    
    // 枚举m的所有约数d，d = h+1 => h = d-1
    ll max_div = sqrt(m);
    for (ll d = 1; d <= max_div; ++d) {
        if (m % d != 0) continue;
        
        // 情况1：d = h+1，v+1 = m/d
        ll h = d - 1;
        ll v_plus_1 = m / d;
        ll v = v_plus_1 - 1;
        // 验证约束条件
        if (h >= 0 && h <= a - 1 && h <= k &&    // h的合法性
            v >= 0 && v <= b - 1 && v == k - h) { // v的合法性
            candidates.emplace_back(h, v);
        }
        
        // 情况2：m/d = h+1，v+1 = d（避免d与m/d相等时重复添加）
        if (d != m / d) {
            ll h2 = (m / d) - 1;
            ll v2_plus_1 = d;
            ll v2 = v2_plus_1 - 1;
            if (h2 >= 0 && h2 <= a - 1 && h2 <= k &&
                v2 >= 0 && v2 <= b - 1 && v2 == k - h2) {
                candidates.emplace_back(h2, v2);
            }
        }
    }
    
    if (candidates.empty()) {
        cout << -1 << "\n";
    } else {
        // 按h升序排序，取最小h的解
        sort(candidates.begin(), candidates.end());
        cout << candidates[0].first << " " << candidates[0].second << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

五、代码解释与复杂度分析

1. 约数枚举：通过math.isqrt(m)获取$\sqrt{m}$，枚举$1$到$\sqrt{m}$的所有整数，判断是否为$m$的约数，同时处理$d$和$m/d$两种约数情况，避免遗漏。
2. 约束验证：对每个约数对应的$h$，计算$v$后逐一验证边界约束，确保切割次数合法。
3. 最优解选择：将所有合法的$(h, v)$对按$h$升序排序，取第一个即为“水平切割次数最少”的解。

复杂度分析

• 时间复杂度：每组测试数据的时间主要用于枚举$m$的约数，为$O(\sqrt{m})$。由于$t \leq 100$且$\sqrt{10^{18}} = 10^9$（但实际因$h \leq \min(a-1, k)$，枚举量会更小），可满足时间要求。
• 空间复杂度：$O(1)$（仅存储少量候选解，可忽略）。

六、算法标签

• 数学推导
• 枚举与验证
• 约束条件分析

七、样例验证

以第三组样例（$a=3, b=5, k=5, m=12$）为例：

1. 枚举$12$的约数：$1, 2, 3, 4, 6, 12$。
2. 对每个约数$d$计算$h = d-1$：
   • $d=3$：$h=2$，$v+1=12/3=4$→$v=3$。验证：$h=2 \leq 3-1=2$（合法），$v=3 \leq5-1=4$（合法），$h+v=5=k$（合法），因此$(2,3)$是合法解。
3. 无其他合法解，输出$(2,3)$，与样例一致。