Bạn được cho các số nguyên $N, K$ và một dãy số nguyên $X = (X_0, X_1, \dots, X_{N-1})$ có độ dài $N$.
Một bộ ba số nguyên $(M, A, B)$ được gọi là một bộ ba tốt nếu nó thỏa mãn tất cả các điều kiện sau:
- $1 \le M < 2^{30}$
- Với mọi $k = 0, 1, \dots, N-1$, biểu thức $X_k = \lfloor \frac{Ak + B}{M} \rfloor$ luôn đúng.
Có thể chứng minh rằng, dưới các ràng buộc đã cho, số lượng bộ ba tốt là hữu hạn. Gọi số lượng này là $C$.
Hãy xác định xem $K \le C$ có đúng hay không. Nếu đúng, hãy tìm bộ ba tốt nhỏ thứ $K$ theo thứ tự từ điển.
Bạn được cho $T$ bộ dữ liệu. Hãy giải từng bộ dữ liệu một cách độc lập.
Dữ liệu vào
Dữ liệu vào được cung cấp theo định dạng sau:
T case1 case2 : caseT
Mỗi bộ dữ liệu $\text{case}_i$ được cung cấp theo định dạng sau:
N K X0 X1 ... XN-1
Ràng buộc
- Tất cả các giá trị đầu vào đều là số nguyên.
- $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}$
- Tổng của $N$ trên tất cả các bộ dữ liệu không vượt quá $2 \times 10^5$.
Dữ liệu ra
In ra $T$ dòng.
Ở dòng thứ $i$, nếu $K \le C$ đúng với bộ dữ liệu thứ $i$, hãy in ra bộ ba tốt nhỏ thứ $K$ theo thứ tự từ điển bằng cách in $M, A, B$ theo đúng thứ tự này, cách nhau bởi dấu cách. Ngược lại, in ra -1.
Ví dụ
Đầu vào 1
3 4 1 0 1 1 2 3 1 2 0 1 6 7 9 8 6 4 2 1
Đầu ra 1
2 1 1 -1 11 -19 107
Ghi chú
Trong ví dụ đầu tiên, các bộ ba tốt theo thứ tự từ điển là $(M, A, B) = (2, 1, 1), (3, 2, 1), (4, 2, 2), (4, 2, 3), (4, 3, 1), \dots$.
Trong ví dụ thứ hai, không tồn tại bộ ba tốt nào.
Trong ví dụ thứ ba, các bộ ba tốt theo thứ tự từ điển là $(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$.