ゼッケンの交換 (Swapping Bibs)

JOI 高校の \(N\) 人の生徒が東西に一列に並んでいる．列の西の端から \(i\) 番目の生徒が生徒 \(i\) である．それぞれの生徒は整数が \(1\) つ書かれたゼッケンを付けている．最初，生徒 \(i\) のゼッケンには整数 \(A_i\) が書かれている．

バトンが \(M\) 個あり，バトンには \(1\) から \(M\) までの番号が付けられている．\(k = 1, 2, \ldots, M\) に対し，以下の操作を行う．バトン \(k\) (\(2 \leqq k \leqq M\)) に関する操作は，バトン \(k - 1\) に関する操作が終わってから行う．

1. 先生がバトン \(k\) を生徒 \(1\) に渡す．
2. バトンを受け取った生徒は，以下のルールに従ってバトンを渡す．
   • ルール：生徒 \(i\) がバトン \(k\) を受け取ったとする．
     • \(1 \leqq i \leqq N - 1\) のとき: 生徒 \(i\) のゼッケンの整数を \(k\) で割った余りが，生徒 \(i + 1\) のゼッケンの整数を \(k\) で割った余りよりも大きいとき，生徒 \(i\) と生徒 \(i + 1\) がゼッケンを交換し，生徒 \(i\) は生徒 \(i + 1\) にバトンを渡す．そうでないときは，ゼッケンを交換せずに，生徒 \(i\) は生徒 \(i + 1\) にバトンを渡す．
     • \(i = N\) のとき: 生徒 \(N\) はバトンを先生に渡す．
3. 先生が生徒 \(N\) からバトン \(k\) を受け取ったら，バトン \(k\) に関する操作は終わりである．

生徒のゼッケンに最初に書かれていた整数とバトンの個数 \(M\) が与えられたとき，先生が生徒 \(N\) からバトン \(M\) を受け取った後の，それぞれの生徒のゼッケンの整数を求めるプログラムを作成せよ．

入力は \(1 + N\) 行からなる．

\(1\) 行目には整数 \(N, M\) (\(1 \leqq N \leqq 100\)，\(1 \leqq M \leqq 100\)) が空白を区切りとして書かれており，それぞれ生徒の人数とバトンの個数を表す．

続く \(N\) 行のうちの \(i\) 行目 (\(1 \leqq i \leqq N\)) には整数 \(A_i\) (\(1 \leqq A_i \leqq 1000\)) が書かれており，生徒 \(i\) のゼッケンに最初に書かれている整数 \(A_i\) を表す．

出力は \(N\) 行からなる．\(i\) 行目 (\(1 \leqq i \leqq N\)) には，先生が生徒 \(N\) からバトン \(M\) を受け取った後の，生徒 \(i\) のゼッケンの整数を出力せよ．

JOI 2016 · JCIOI · CC BY-SA 4.0