整数 $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$ です。
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), \dots$ です。