給你整數 $N, K$ 以及一個長度為 $N$ 的整數序列 $X = (X_0, X_1, \dots, X_{N-1})$。
如果一個整數三元組 $(M, A, B)$ 滿足以下所有條件,則稱其為優秀三元組:
- $1 \le M < 2^{30}$
- 對於所有 $k = 0, 1, \dots, N-1$,均滿足 $X_k = \lfloor \frac{Ak + B}{M} \rfloor$。
可以證明,在給定的限制條件下,優秀三元組的數量是有限的。設該數量為 $C$。
確定 $K \le C$ 是否成立。如果成立,求出按字典序排列的第 $K$ 小的優秀三元組。
給你 $T$ 組測試資料。獨立求解每組測試資料。
輸入格式
輸入格式如下:
T case1 case2 : caseT
每組測試資料 $\text{case}_i$ 的格式如下:
N K X0 X1 ... XN-1
資料範圍
- 所有輸入值均為整數。
- $1 \le T \le 1000$
- $2 \le N \le 2 \times 10^5$
- $1 \le K \le 10^9$
- $0 \le X_i < 2^{30}$
- 所有測試資料的 $N$ 總和不超過 $2 \times 10^5$。
輸出格式
輸出 $T$ 行。
對於第 $i$ 行,如果第 $i$ 組測試資料滿足 $K \le C$,則輸出按字典序排列的第 $K$ 小的優秀三元組,即依序輸出 $M, A, B$,中間用空格分隔。否則,輸出 -1。
範例
輸入範例 1
3 4 1 0 1 1 2 3 1 2 0 1 6 7 9 8 6 4 2 1
輸出範例 1
2 1 1 -1 11 -19 107
說明
在第一個範例中,按字典序排列的優秀三元組依序為 $(M, A, B) = (2, 1, 1), (3, 2, 1), (4, 2, 2), (4, 2, 3), (4, 3, 1), \dots$。
在第二個範例中,不存在優秀三元組。
在第三個範例中,按字典序排列的優秀三元組依序為 $(M, A, B) = (4, -7, 39), (7, -12, 68), (8, -14, 78), (8, -14, 79), (9, -16, 89), (10, -17, 97), (11, -19, 107), \dots$。