L - Linear Floor Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

整数 N,K と長さ N の整数列 X=(X_0,X_1,\ldots,X_{N-1}) が与えられます。

以下の条件を全て満たす整数の組 (M,A,B) を良い組と呼びます。

  • 1 \le M < 2^{30}
  • k=0,1,\ldots,N-1 に対し \displaystyle X_k = \left\lfloor\frac{Ak+B}M \right\rfloor が成り立つ。

制約下で良い組の個数は有限となることが証明できます。この個数を C とします。

K \le C が成り立つか判定し、成り立つ場合は辞書順で K 番目に小さい良い組を求めてください。

T 個のテストケースが与えられるので、それぞれについて答えてください。

制約

  • 入力は全て整数
  • 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 以下

部分点

  • 追加の制約 K=1 を満たすデータセットに正解した場合は 2 点が与えられる。
  • 追加の制約 K\le 10 を満たすデータセットに正解した場合はさらに 18 点が与えられる。

入力

入力は以下の形式で標準入力から与えられる。

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

i 番目のテストケース \text{case}_i は以下の形式で与えられる。

N K
X_0 X_1 \ldots X_{N-1}

出力

T 行出力せよ。

i 行目には、 \text{case}_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

1 番目のテストケースについて、良い組は辞書順に (M,A,B)=(2,1,1),(3,2,1),(4,2,2),(4,2,3),(4,3,1),\ldots です。

2 番目のテストケースについて、良い組は存在しません。

3 番目のテストケースについて、良い組は辞書順に (M,A,B)=(4,-7,39),(7,-12,68),(8,-14,78),(8,-14,79),(9,-16,89),(10,-17,97),(11,-19,107),\ldots です。