You are given integers $N, K$ and an integer sequence $X = (X_0, X_1, \dots, X_{N-1})$ of length $N$.
An integer triple $(M, A, B)$ is called a good triple if it satisfies all of the following conditions:
- $1 \le M < 2^{30}$
- For all $k = 0, 1, \dots, N-1$, $X_k = \lfloor \frac{Ak + B}{M} \rfloor$ holds.
It can be proven that, under the given constraints, the number of good triples is finite. Let this number be $C$.
Determine whether $K \le C$ holds. If it does, find the $K$-th smallest good triple in lexicographical order.
You are given $T$ test cases. Solve each test case independently.
Input
The input is given in the following format:
T case1 case2 : caseT
Each test case $\text{case}_i$ is given in the following format:
N K X0 X1 ... XN-1
Constraints
- All input values are integers.
- $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}$
- The sum of $N$ over all test cases does not exceed $2 \times 10^5$.
Output
Print $T$ lines.
For the $i$-th line, if $K \le C$ holds for the $i$-th test case, output the $K$-th smallest good triple in lexicographical order by printing $M, A, B$ in this order separated by spaces. Otherwise, output -1.
Example
Input 1
3 4 1 0 1 1 2 3 1 2 0 1 6 7 9 8 6 4 2 1
Output 1
2 1 1 -1 11 -19 107
Note
In the first example, the good triples in lexicographical order are $(M, A, B) = (2, 1, 1), (3, 2, 1), (4, 2, 2), (4, 2, 3), (4, 3, 1), \dots$.
In the second example, no good triple exists.
In the third example, the good triples in lexicographical order are $(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$.