畀你整數 $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$。