問題一覧 > 通常問題

No.1013 〇マス進む

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 89
作問者 : otamay6otamay6 / テスター : 37zigen37zigen
5 ProblemId : 3604 / 出題時の順位表
問題文最終更新日: 2019-12-08 15:25:37

問題文

{$1,2, \dots ,N$} を並び替えた順列 $P$ が与えられます。
$P$ を $10^{10}$ 個繋げた数列を $T$ とします。
あなたは $T$ 上で以下の行動を行います。
・$i$ 番目の要素にいるとき、 $i+T_i$ 番目の要素に移動する
最初に $i$ 番目 $(i=1,2, \dots ,N)$ の要素にいるとき、このような行動を $K$ 回行ったのち
何番目の要素にたどり着くかを、全ての $i$ に対してそれぞれ求めて1行ずつ出力してください。

入力

$N\ K$
$P_1\ P_2\ \dots\ P_N$

入力は整数で与えられる
$ 1 \le N \le 10^5 $
$ 1 \le K \le 10^9 $
$P$ は {$1, 2, \dots , N$} を並び替えた順列である。

出力

$A_1$
$A_2$
$\vdots$
$A_N$

$i (i=1,2, \dots , N)$ についての問題の答え $A_i$ を上の形式で出力してください。
最後に改行してください。

サンプル

サンプル1
入力
5 2
1 2 3 4 5
出力
4
8
7
11
15

例えば、3番目からスタートすると、3→6→7と進みます。

サンプル2
入力
4 2
1 2 3 4
出力
4
8
8
12

サンプル3
入力
10 6
1 9 5 10 2 4 3 8 7 6
出力
31
32
36
64
30
36
36
40
40
40

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。