Linear Floor
给定整数 N,K 和长度为 N 的整数序列 X=(X0,X1,…,XN−1)。
称整数三元组 (M,A,B) 为合法三元组,当且仅当:
- 1≤M<230;
- 对所有 k=0,…,N−1,都有 Xk=⌊MAk+B⌋。
⌊⋅⌋ 表示向下取整。A 和 B 是整数,不额外要求为正;特别地,A 可以为负。
可以证明合法三元组总数是有限的。请找出按字典序排序后的第 K 个合法三元组;若总数不足 K,输出 −1。比较三元组时依次比较 M、A、B。
输入格式
第一行一个整数 T。每个测试用例先输入一行 N,K,再输入一行 N 个整数 X0,…,XN−1。
输出格式
每个测试用例输出一行。若不存在第 K 个合法三元组,输出 -1;否则输出 M,A,B,以空格分隔。
数据范围
1≤T≤1000,2≤N≤2×105,1≤K≤109,0≤Xi<230。单个输入文件内所有测试用例的 N 之和不超过 2×105。
样例 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