Problem Description

This is a problem.
This is a problem from Xmas Contest 2015.
This is a problem from Xmas Contest 2015 about strings.
This is a problem from Xmas Contest 2015 about strings and involves generating many strings based on recurrence relations.
This is a problem from Xmas Contest 2015 about strings and involves generating many strings based on recurrence relations and finding their periods.
This is a problem from Xmas Contest 2015 about strings and involves generating many strings based on recurrence relations and finding their periods, but you have to get AC in the next 4 hours.

My favorite thing is programming contests. My dream is to solve all the problems in Xmas Contest 2015. Even in 2016, I will be kind to the contest system.

(Reference: https://twitter.com/kyuridenamida/status/678495822946811904)

Using an integer sequence $ A $ of $ N $ elements and a string $ C $ consisting of $ N $ lowercase English letters, generate $ N+1 $ strings $ S_0, S_1, ..., S_N $ as follows:

• First, let $ S_0 $ be an empty string.
• For $ i = 1, 2, ..., N $, the string $ S_i $ is formed by appending the $ i $-th character of $ C $ to the end of the string $ S_{A_i} $. For any $ i $, it holds that $ A_i < i $.

For the $ N $ strings $ S_1, S_2, ..., S_N $ generated in this way, find their periods.

The period of a string $ T $ is the length of the shortest string $ X $ such that $ T $ is a prefix of the infinite repetition of $ X $. For example, the period of abcabca is $ 3 $, and the period of abcabd is $ 6 $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_1 $ $ A_2 $ … $ A_N $ $ C $

• The first line contains the integer $N\ (1 \leq N \leq 5 \times 10^5)$.
• The second line contains the integer sequence $ A $ of $ N $ elements separated by spaces. For all $i\ (1 \leq i \leq N)$, it satisfies $0 \leq A_i < i$.
• The third line contains the string $ C $ of $ N $ characters, consisting only of lowercase English letters.

Output Format

Output $ N $ lines. The $ i $-th line ($1 \leq i \leq N$) should contain a single integer representing the period of the string $ S_i $.

Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

8
0 1 2 3 4 5 6 5
abcabcad

Sample Output #1

1
2
3
3
3
3
3
6

Sample Input #2

11
0 0 1 2 3 1 2 5 4 3 6
xmascontest

Sample Output #2

1
1
2
2
3
2
2
4
3
3
3

Notes/Hints

Sample Explanation 1

In this example, each $ S_i $ and its period are as follows:
- $ S_1 $ is a, and its period is $ 1 $.
- $ S_2 $ is ab, and its period is $ 2 $.
- $ S_3 $ is abc, and its period is $ 3 $.
- $ S_4 $ is abca, and its period is $ 3 $.
- $ S_5 $ is abcab, and its period is $ 3 $.
- $ S_6 $ is abcabc, and its period is $ 3 $.
- $ S_7 $ is abcabca, and its period is $ 3 $.
- $ S_8 $ is abcabd, and its period is $ 6 $.

见题面 Input 部分

见题面 Output 部分