AT_utpc2025_l Linear Floor

整数 $ 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 $ 個のテストケースが与えられるので、それぞれについて答えてください。

入力は以下の形式で標準入力から与えられる。 > $ 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` を出力せよ。

### 部分点 - 追加の制約 $ K=1 $ を満たすデータセットに正解した場合は $ 2 $ 点が与えられる。 - 追加の制約 $ K\le 10 $ を満たすデータセットに正解した場合はさらに $ 18 $ 点が与えられる。 ### Sample Explanation 1 $ 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 $ です。 ### Constraints - 入力は全て整数 - $ 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 $ 以下