H - K-th Shifted Array

2 secs 1024 MB
uni_kakurenbo

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


配点:

問題文


長さ の整数列 があります.

また,次の操作を 回以上何度でも行うことができます:

  • を左に 要素分だけ循環シフトする.すなわち列 によって定められる列 で置き換える.

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

  • なお,任意の長さ 数列 とにおいて,以下がいずれも成り立つ:
    • とが異なる」とは『ある整数 が存在して, である』ことに等しい.
    • より辞書順で小さい」とは『ある整数 が存在して,任意の なる整数 について であり,かつ である』ことに等しい.

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

制約


  • 入力はすべて整数
  • に対して 回以上の操作を行うことによって得られる相異なる列は 個以上存在する.

入力


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


出力


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

サンプル


入力例1
1
5 1
3 1 2 1 5
出力例1
1 2 1 5 3

ちょうど 回操作を行って得られる列 が辞書順で最小です.


入力例2
1
6 2
1 2 1 2 1 2
出力例2
2 1 2 1 2 1

操作によって得られる相異なる列は もしくは つのみです.
回のうちいずれかの回数の操作を行ったとき, は,上記 つのうち辞書順で 番目に小さい列である をとります.

提出


Go (1.14)