Swapping Bibs

Time Limit : 8 sec, Memory Limit : 262144 KB

ゼッケンの交換 (Swapping Bibs)

問題

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

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

  1. 先生がバトン k を生徒 1 に渡す.
  2. バトンを受け取った生徒は,以下のルールに従ってバトンを渡す.
    • ルール:生徒 i がバトン k を受け取ったとする.
      • 1 ≦ i ≦ 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 ≦ N ≦ 100, 1 ≦ M ≦ 100) が空白を区切りとして書かれており,それぞれ生徒の人数とバトンの個数を表す.

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

出力

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

入出力例

入力例 1

6 4
3
2
8
3
1
5

出力例 1

2
3
1
8
5
3

入力例 2

10 6
1
2
3
4
5
6
7
8
9
10

出力例 2

6
1
2
3
10
4
8
7
9
5

入出力例 1 では 6 人の生徒がいる.最初,生徒のゼッケンは順に 3, 2, 8, 3, 1, 5 である.バトンは 4 個ある.

  • バトン 1 に関する操作が終了した時点での生徒のゼッケンは順に 3, 2, 8, 3, 1, 5 である.
  • バトン 2 に関する操作が終了した時点での生徒のゼッケンは順に 2, 8, 3, 3, 1, 5 である.
  • バトン 3 に関する操作が終了した時点での生徒のゼッケンは順に 2, 3, 3, 1, 8, 5 である.
  • バトン 4 に関する操作が終了した時点での生徒のゼッケンは順に 2, 3, 1, 8, 5, 3 である.

Source: 15th Japanese Olympiad in Informatics , 2015-12-13
http://www.ioi-jp.org/