#P18009. Linear Floor

Linear Floor

Linear Floor

给定整数 N,KN,K 和长度为 NN 的整数序列 X=(X0,X1,…,XN−1)X=(X_0,X_1,\ldots,X_{N-1})。

称整数三元组 (M,A,B)(M,A,B) 为合法三元组,当且仅当:

  • 1≤M<2301\le M<2^{30};
  • 对所有 k=0,…,N−1k=0,\ldots,N-1,都有 Xk=⌊Ak+BM⌋X_k=\left\lfloor\dfrac{Ak+B}{M}\right\rfloor。

⌊⋅⌋\lfloor\cdot\rfloor 表示向下取整。AA 和 BB 是整数,不额外要求为正;特别地,AA 可以为负。

可以证明合法三元组总数是有限的。请找出按字典序排序后的第 KK 个合法三元组;若总数不足 KK,输出 −1-1。比较三元组时依次比较 MM、AA、BB。

输入格式

第一行一个整数 TT。每个测试用例先输入一行 N,KN,K,再输入一行 NN 个整数 X0,…,XN−1X_0,\ldots,X_{N-1}。

输出格式

每个测试用例输出一行。若不存在第 KK 个合法三元组,输出 -1;否则输出 M,A,BM,A,B,以空格分隔。

数据范围

1≤T≤10001\le T\le1000,2≤N≤2×1052\le N\le2\times10^5,1≤K≤1091\le K\le10^9,0≤Xi<2300\le X_i<2^{30}。单个输入文件内所有测试用例的 NN 之和不超过 2×1052\times10^5。

样例 1

输入

3
4 1
0 1 1 2
3 1
2 0 1
6 7
9 8 6 4 2 1

输出

2 1 1
-1
11 -19 107