AT_abc013_4 [ABC013D] 阿弥陀

[problemUrl]: https://atcoder.jp/contests/abc013/tasks/abc013_4 古くより伝わる日本の伝統的なくじ引き、あみだくじをご存知だろうか？ あみだくじを行うときは、まず $ N $ 本の平行な縦線を引く。次に、$ M $ 本の横線をその中に引いていく。それぞれの横線は隣り合う $ 2 $ 本の縦線を結ぶように引かなければならず、$ 2 $ 本以上の横線がまったく同じ高さにあってはいけない。ここでは、上から $ i $ ($ 1\,≦\,i\,≦\,M $) 番目にある横線が、左から $ A_i $ ($ 1\,≦\,A_i\ )\ 番目の縦線と\ A_i\ +\ 1 $ 番目の縦線を結んでいるとしよう。 $ N\ =\ 5 $, $ M\ =\ 7 $, $ A\ =\ \{1,4,3,4,2,3,1\} $ の場合のあみだくじを以下に示す。くじを引くときは、縦線を $ 1 $ 本選び、その上端から線を下っていく。途中で横線に遭遇したときには必ず曲がらなければならず、また縦線を上向きに辿ってはいけない。たとえばこのあみだくじで左から $ 4 $ 番目の縦線から始めてくじを引くと、左から $ 3 $ 番目の縦線に辿り着く。  さて、ここまでは普通のあみだくじであるが、何かにつけビッグデータという言葉が騒がれる昨今である。あみだくじがこれから先生きのこるためには、あみだくじもビッグになってビッグデータに対抗していかなければならない。 そこで、あみだくじを縦に $ D $ 個つなげることで巨大なあみだくじを作ることを考えよう。たとえば、先ほど例に挙げたあみだくじを $ 2 $ 個つなげてみると以下のようになる。この場合、左から $ 4 $ 番目の縦線から始めてくじを引くと、辿り着く場所は左から $ 5 $ 番目の縦線になる。  こうして作った巨大あみだくじだが、あみだくじ本来の目的を果たせなければビッグになった意味もない。つまり、この巨大なあみだくじを使ってくじを引いた結果がどうなるかを効率よく計算できなければ、せっかく作った巨大あみだくじもただの落書きである。 そこで、$ 1\,≦\,k\,≦\,N $ を満たすすべての整数 $ k $ に対し、巨大あみだくじの左から $ k $ 番目の縦線を選んで線を辿っていったとき、最終的に下端で左から何番目の縦線に行き着くかを計算するプログラムを書いて欲しい。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ D $ $ A_1 $ $ A_2 $ $ ... $ $ A_M $ - $ 1 $ 行目には、元のあみだくじの縦線の本数を表す整数 $ N $ ($ 2\,≦\,N\,≦\,10^5 $)、横線の本数を表す整数 $ M $ ($ 0\,≦\,M\,≦\,2\ \times\ 10^5 $)、元のあみだくじを縦につなげる回数を表す整数 $ D $ ($ 1\,≦\,D\,≦\,10^9 $) が空白区切りで与えられる。 - $ 2 $ 行目には、元のあみだくじにおける横線の情報を表す $ M $ 個の整数 $ A_i $ ($ 1\,≦\,i\,≦\,M $) が空白区切りで与えられる。

$ N $ 行出力せよ。このうち $ k $ 行目には、巨大あみだくじの左から $ k $ 番目の縦線を選んで線を辿っていったとき、下端で左から何番目の縦線に到達するかを表す整数を出力せよ。 出力の末尾にも改行をいれること。

### 部分点 この問題のテストケースは $ 4 $ つのグループに分けられており、それぞれに配点が決まっている。 - $ 1 $ つめのグループにおいて、テストケースは $ D\ =\ 1 $ を満たす。このグループのテストケース全てに正解すると $ 10 $ 点が与えられる。 - $ 2 $ つめのグループにおいて、テストケースは $ N\,≦\,1,000 $ および $ D\,≦\,1,000 $ を満たす。このグループのテストケース全てに正解すると $ 20 $ 点が与えられる。 - $ 3 $ つめのグループにおいて、テストケースは $ N\,≦\,8 $ を満たす。このグループのテストケース全てに正解すると $ 20 $ 点が与えられる。 - $ 4 $ つめのグループにおいてはテストケースに追加の制限はない。このグループのテストケース全てに正解すると $ 50 $ 点が与えられる。 ### Sample Explanation 1 この入出力例は問題文中の最初の図で示されたあみだくじに対応している。 ### Sample Explanation 2 この入出力例は問題文中の $ 2 $ 番目の図で示されたあみだくじに対応している。このケースは $ 1 $ つめのテストグループの制約を満たさないことに注意せよ。 ### Sample Explanation 3 このケースは $ 1 $ つめおよび $ 3 $ つめのテストグループの制約を満たさないことに注意せよ。