Anda diberikan bilangan bulat $N, K$ dan sebuah barisan bilangan bulat $X = (X_0, X_1, \dots, X_{N-1})$ dengan panjang $N$.
Sebuah tripel bilangan bulat $(M, A, B)$ disebut tripel baik jika memenuhi semua kondisi berikut:
- $1 \le M < 2^{30}$
- Untuk semua $k = 0, 1, \dots, N-1$, berlaku $X_k = \lfloor \frac{Ak + B}{M} \rfloor$.
Dapat dibuktikan bahwa, di bawah batasan yang diberikan, banyaknya tripel baik adalah berhingga. Misalkan banyaknya ini adalah $C$.
Tentukan apakah $K \le C$ berlaku. Jika berlaku, carilah tripel baik terkecil ke-$K$ dalam urutan leksikografis.
Anda diberikan $T$ kasus uji. Selesaikan setiap kasus uji secara independen.
Masukan
Masukan diberikan dalam format berikut:
T case1 case2 : caseT
Setiap kasus uji $\text{case}_i$ diberikan dalam format berikut:
N K X0 X1 ... XN-1
Batasan
- Semua nilai masukan adalah bilangan bulat.
- $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}$
- Jumlah $N$ di semua kasus uji tidak melebihi $2 \times 10^5$.
Keluaran
Cetak $T$ baris.
Untuk baris ke-$i$, jika $K \le C$ berlaku untuk kasus uji ke-$i$, keluarkan tripel baik terkecil ke-$K$ dalam urutan leksikografis dengan mencetak $M, A, B$ dalam urutan ini yang dipisahkan oleh spasi. Jika tidak, keluarkan -1.
Contoh
Masukan 1
3 4 1 0 1 1 2 3 1 2 0 1 6 7 9 8 6 4 2 1
Keluaran 1
2 1 1 -1 11 -19 107
Catatan
Pada contoh pertama, tripel-tripel baik dalam urutan leksikografis adalah $(M, A, B) = (2, 1, 1), (3, 2, 1), (4, 2, 2), (4, 2, 3), (4, 3, 1), \dots$.
Pada contoh kedua, tidak ada tripel baik.
Pada contoh ketiga, tripel-tripel baik dalam urutan leksikografis adalah $(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$.