B - 迷子のCDケース
Editorial
/
高橋君はCDで音楽を聴くことが好きです。
CDプレイヤーには先日聴いたCDが入ったままになっているのですが、そのCDに対応するCDケースが見当たらないことに気づきました。
前回に聴いた時にCDケースをどこに置いたのか、残念ながら高橋君は全く思い出せませんでした。
仕方がないので高橋君は今から聴こうとしているCDをケースから取り出し、CDプレイヤーに入っていたCDをそのケースへと片付けることにしました。
さらに別のCDを新たにCDプレイヤーに入れる場合も、CDプレイヤーに入っていたCDは空いたCDケースに片づけます。 例えば図 1 のように 3 枚のCDがある状態で、黄緑色のCD、オレンジ色のCDの順でCDを聴くと、それぞれのCDは最も下の図のように片付けられることになります。 高橋君が音楽を聴き終わった後、今日聞いたCDのリストが与えられるので、高橋君が所持するCDケースにはそれぞれどのCDが入っているかを答えなさい。
入力は以下の形式で標準入力から与えられる。
1 から N 番までのCDケースに入ってるCDの番号を順に標準出力に 1 行に 1 ケース分ずつ出力せよ。
なお、最後には改行を出力せよ。
Time Limit: 2 sec / Memory Limit: 64 MB
問題文
CDプレイヤーには先日聴いたCDが入ったままになっているのですが、そのCDに対応するCDケースが見当たらないことに気づきました。
前回に聴いた時にCDケースをどこに置いたのか、残念ながら高橋君は全く思い出せませんでした。
仕方がないので高橋君は今から聴こうとしているCDをケースから取り出し、CDプレイヤーに入っていたCDをそのケースへと片付けることにしました。
さらに別のCDを新たにCDプレイヤーに入れる場合も、CDプレイヤーに入っていたCDは空いたCDケースに片づけます。 例えば図 1 のように 3 枚のCDがある状態で、黄緑色のCD、オレンジ色のCDの順でCDを聴くと、それぞれのCDは最も下の図のように片付けられることになります。 高橋君が音楽を聴き終わった後、今日聞いたCDのリストが与えられるので、高橋君が所持するCDケースにはそれぞれどのCDが入っているかを答えなさい。
入力
N M disk_{0} disk_{1} : : disk_{M-1}
- 入力は M+1 行ある。
- 1 行目には、高橋君が所持するCDケースの個数を表す整数 N(1≦N≦100)と、今日聴いたCDの枚数 M(0≦M≦100) が空白区切りで与えられる。
- CDケースを 1 つ無くしているので、高橋君は計 N+1 枚のCDを所持している。
- CDと対応するCDケースにはそれぞれ 0 から N までの数が番号付けられている。
- 現在CDプレイヤーに入ってるCDとそれに対応する見当たらないCDケースは 0 番である。
- 2 行目からの M 行には今日聴いたCDの番号のリストが与えられる。
- i+2 行目の整数 disk_{i}(0≦i≦M-1, 0≦disk_i≦N) は i+1 番目に disk_i 番のCDを聴いたことを表している。
出力
なお、最後には改行を出力せよ。
入力例 1
5 6 2 3 5 0 1 3
出力例 1
0 5 2 4 1
- まず 2番のCDを聴くので、0 番のCDは 2 番のCDケースに入れます。
- 次に 3番のCDを聴くので、2 番のCDは 3 番のCDケースに入れます。
- このように各CDを順に聴いては片付けるを繰り返すと、下図のようにCDの位置が入れ替わります。
入力例 2
3 5 0 1 1 1 2
出力例 2
0 1 3
- 同じCDを連続して聴いた場合もあります。
- この場合は 1 枚目としてCDプレイヤーに入っている 0 番のCDを聴くので、CDケースに入っているCDは入れ替わりません。
- 2 枚目としては 1 番のCDを聴くので、1 番のCDケースに 0 番のCDが入ります。
- 3 枚目と 4 枚目は 2 枚目でCDケースに入れた 1 番のCDを聴くので入れ替わりは起きません。
- 最後に 2 番のCDを聴くので 2 番のCDケースに 3 番のCDが入ります。
入力例 3
5 0
出力例 3
1 2 3 4 5
- 何もCDを聴かなかった場合は入れ替わりは起きません。
入力例 4
10 7 2 8 5 3 3 8 1
出力例 4
8 0 5 4 3 6 7 2 9 10
入力例 5
5 7 3 4 3 1 2 2 0
出力例 5
3 1 2 4 5