AT_utpc2025_l Linear Floor

给定整数 $N, K$ 和一个长度为 $N$ 的整数序列 $X = (X_0, X_1, \ldots, X_{N-1})$。 满足以下所有条件的整数三元组 $(M, A, B)$ 被称为**良好组合**： - $1 \leq M < 2^{30}$ - 对于 $k = 0, 1, \ldots, N-1$，都有 $X_k = \left\lfloor \frac{A k + B}{M} \right\rfloor$。 可以证明，在题目限定的条件下，良好组合的个数是有限的。记这个数量为 $C$。 请判断 $K \leq C$ 是否成立。如果成立，输出按字典序排列的第 $K$ 小的良好组合；否则输出 `-1`。 有 $T$ 个测试用例，请分别作答。

输入通过标准输入给出，格式如下： > $T$ $\text{case}_1$ $\text{case}_2$ $\vdots$ $\text{case}_T$ 第 $i$ 个测试用例 $\text{case}_i$ 的格式如下： > $N$ $K$ $X_0$ $X_1$ $\ldots$ $X_{N-1}$

请输出 $T$ 行。 对于第 $i$ 个测试用例，如果 $K \leq C$ 成立，则输出按字典序第 $K$ 小的良好组合 $M, A, B$，以半角空格分隔；否则输出 `-1`。

### 部分分 - 对于满足附加条件 $K = 1$ 的数据集，得到 2 分。 - 对于满足附加条件 $K \leq 10$ 的数据集，得到额外 18 分。 ### 样例说明 1 对于第 $1$ 个测试用例，所有良好组合按字典序依次是 $(M, A, B) = (2, 1, 1), (3, 2, 1), (4, 2, 2), (4, 2, 3), (4, 3, 1), \ldots$。 对于第 $2$ 个测试用例，不存在良好组合。 对于第 $3$ 个测试用例，良好组合按字典序依次为 $(M, A, B) = (4, -7, 39), (7, -12, 68), (8, -14, 78), (8, -14, 79), (9, -16, 89), (10, -17, 97), (11, -19, 107), \ldots$。 ### 约束条件 - 所有输入均为整数。 - $1 \leq T \leq 1000$ - $2 \leq N \leq 2 \times 10^5$ - $1 \leq K \leq 10^9$ - $0 \leq X_i < 2^{30}$ - 所有测试用例中的 $N$ 总和不超过 $2 \times 10^5$。 由 ChatGPT 5 翻译