マルチテストについての説明はこちら (サンプル問題を確認されていない方のみお読みください。)

配点：$300$ 点

問題文

長さ $N$ の整数列 $A = (A_1, A_2, \ldots, A_N)$ があります．

また，次の操作を $0$ 回以上何度でも行うことができます：

• $A$ を左に $1$ 要素分だけ循環シフトする．すなわち列 $A$ を $A'_i = A_{(i + 1) \bmod N} \scriptsize \; (1 \leq i \leq N)$ によって定められる列 $(A'_1, A'_2, \ldots, A'_N)$ で置き換える．

$A$ に対して以上の操作を繰り返し行うことよって達成できる相異なる列であって辞書順で $K$ 番目に小さいものを求めてください．

• なお，任意の長さ $l$ の $2$ 数列 $x = (x_1, x_2, \ldots, x_l)$ と $y = (y_1, y_2, \ldots, y_l)$ とにおいて，以下がいずれも成り立つ：
  • 「$x$ と $y$ とが異なる」とは『ある整数 $i \; \scriptsize(1 \leq i \leq l)$ が存在して，$x_i \not= y_i$ である』ことに等しい．
  • 「$x$ が $y$ より辞書順で小さい」とは『ある整数 $i \; \scriptsize(1 \leq i \leq l)$ が存在して，任意の $1 \leq j < i$ なる整数 $j$ について $x_j = y_j$ であり，かつ $x_i < y_i$ である』ことに等しい．

ここで，操作によって達成することのできる相異なる列は，必ず $K$ 個以上存在することを保証します．

制約

• $1 \leq \Phi \leq 10^5$
• $1 \leq K \leq N$
• $\sum_{\phi} \Phi_{\phi}(N) \leq 10^5$
• $|A_i| < 2^{30} \scriptsize \; (1 \leq i \leq N)$
• 入力はすべて整数
• $A$ に対して $0$ 回以上の操作を行うことによって得られる相異なる列は $K$ 個以上存在する．

入力

各テストケースの入力は，それぞれ以下の形式で与えられる：

出力

答えとなる列を，要素ごとに空白もしくは改行で区切って出力せよ．

サンプル

1
5 1
3 1 2 1 5

1 2 1 5 3

ちょうど $1$ 回操作を行って得られる列 $(1, 2, 1, 5, 3)$ が辞書順で最小です．

1
6 2
1 2 1 2 1 2

2 1 2 1 2 1

操作によって得られる相異なる列は $(1, 2, 1, 2, 1, 2)$ もしくは $(2, 1, 2, 1, 2, 1)$ の $2$ つのみです．
$1, 3, 5, 7, 9, \ldots$ 回のうちいずれかの回数の操作を行ったとき，$A$ は，上記 $2$ つのうち辞書順で $2$ 番目に小さい列である $(2, 1, 2, 1, 2, 1)$ をとります．