给你整数 $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$。