AT_xmascontest2015_d Destroy the Duplicated Poem

[problemUrl]: https://atcoder.jp/contests/xmascontest2015noon/tasks/xmascontest2015_d これは問題です。 これは Xmas Contest 2015 の問題です。 これは Xmas Contest 2015 の問題で文字列に関するものです。 これは Xmas Contest 2015 の問題で文字列に関するもので漸化式に基づいてたくさんの文字列を作ります。 これは Xmas Contest 2015 の問題で文字列に関するもので漸化式に基づいてたくさんの文字列を作ってそれらの周期を求めます。 これは Xmas Contest 2015 の問題で文字列に関するもので漸化式に基づいてたくさんの文字列を作ってそれらの周期を求めるけどあと 4 時間で AC しないといけません。 ぼくのすきな事はプログラミングコンテストです。 ぼくのゆめは Xmas Contest 2015 で全部の問題を解くことです。2016 年になってもコンテストシステムにやさしくします。 (参考: ) - - - - - - $ N $ 要素の整数列 $ A $ と、$ N $ 文字の英小文字からなる文字列 $ C $ を使って以下のように $ N+1 $ 個の文字列 $ S_0,\ S_1,\ ...,\ S_N $ を生成する。 - まず $ S_0 $ を空文字列とする。 - $ i\ =\ 1,\ 2,\ ...,\ N $ について、文字列 $ S_i $ は文字列 $ S_{A_i} $ の末尾に $ C $ の $ i $ 番目の文字を付け加えたものである。ただし、任意の $ i $ について $ A_i\

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ … $ A_N $ $ C $ - $ 1 $ 行目には整数 $ N\ (1≦N≦5\ \times\ 10^5) $ が与えられる。 - $ 2 $ 行目には $ N $ 要素の整数列 $ A $ が空白区切りで与えられる。すべての $ i\ (1≦i≦N) $ に対し $ 0≦A_i\

$ N $ 行出力せよ。そのうち $ i\ (1≦i≦N) $ 行目には文字列 $ S_i $ の周期を表す整数を $ 1 $ つ出力せよ。 出力の末尾にも改行を入れること。

### Sample Explanation 1 この例において各 $ S_i $ とその周期は次のようになる。 - $ S_1 $ は `a` となり、その周期は $ 1 $ である。 - $ S_2 $ は `ab` となり、その周期は $ 2 $ である。 - $ S_3 $ は `abc` となり、その周期は $ 3 $ である。 - $ S_4 $ は `abca` となり、その周期は $ 3 $ である。 - $ S_5 $ は `abcab` となり、その周期は $ 3 $ である。 - $ S_6 $ は `abcabc` となり、その周期は $ 3 $ である。 - $ S_7 $ は `abcabca` となり、その周期は $ 3 $ である。 - $ S_8 $ は `abcabd` となり、その周期は $ 6 $ である。