D - カードの並び替え Editorial /

Time Limit: 10 sec / Memory Limit: 256 MB

配点： 100 点

問題

1 から 2n の数が書かれた 2n 枚のカードがあり，上から 1, 2, 3, \ldots, 2n の順に積み重なっている．

このカードを，次の方法を何回か用いて並べ替える．

整数 k でカット

上から k 枚のカードの山 A と 残りのカードの山 B に分けた後，山 A の上に山 B をのせる．

card01.png

リフルシャッフル

上から n 枚の山 A と残りの山 B に分け，上から A の 1 枚目，B の 1 枚目，A の 2 枚目，B の 2 枚目，\ldots，A の n 枚目，B の n 枚目，となるようにして，1 つの山にする．

card02.png

入力の指示に従い，カードを並び替えたあとのカードの番号を，上から順番に出力するプログラムを作成せよ．

入力

  • 1 行目には n (1 \leqq n \leqq 100) が書かれている．すなわちカードの枚数は 2n 枚である．
  • 2 行目には操作の回数 m (1 \leqq m \leqq 1000) が書かれている．
  • 3 行目から m + 2 行目までの m 行には，0 から 2n - 1 までのいずれか 1 つの整数 k が書かれており，カードを並べ替える方法を順に指定している．
    • k = 0 の場合は，リフルシャッフルを行う．
    • 1 \leqq k \leqq 2n-1 の場合は，k でカットを行う．

出力

2n 行出力せよ．1 行目には並べ替え終了後の一番上のカードの番号，2 行目には並べ替え終了後の上から 2 番目のカードの番号というように，i 行目には上から i 番目のカードの番号を出力せよ．

入力例 1

2
2
1
0

出力例 1

2
4
3
1

入力例 2

3
4
2
4
0
0

出力例 2

1
5
4
3
2
6