33OJ
登录 注册

#P17742. [ICPC 2019 Xuzhou R] Loli, Yen-Jen, and a cool problem

[ICPC 2019 Xuzhou R] Loli, Yen-Jen, and a cool problem

Problem Description

Now, Yen-Jen is solving a problem with a cute catgirl. But he drinks too much yesterday and his mind is not open yet, so he asked you to solve the following problem for him!

Given a rooted tree with NN vertices (vertices are numbered from 11 to NN) whose root is 11. In every node, there's an uppercase letter on it.

Define one way to generate a string with length LL as follows:

  • select a start node XX
  • go to the parent node L−1L - 1 times
  • whenever goes to a node, append the corresponding English letter to the end of the string

Now there are QQ queries, in the ithi^{th} query, a start node XiX_i is given. Please count the number of starting node YY (include XiX_i), such that YY can generate the same string as XiX_i.

Input Format

The first line of the input contains two integer N,QN, Q which is mentioned above.

In the next line, a string SS is given, the ithi^{th} character means the English letter on the ithi^{th} node.

Then, there are N−1N - 1 integers in one line, the ithi^{th} integer is the parent of node i+1i + 1.

Then, there are QQ lines, the ithi^{th} line represents the ithi^{th} query. In each line, Xi,LiX_i, L_i is given, which is mentioned in the description.

It is guaranteed that the testcase is valid!

  • 1≤N,Q≤3×1051 \leq N, Q \leq 3 \times 10 ^ 5
  • 1≤Xi,Li≤N1 \leq X_i, L_i \leq N

Output Format

Output QQ lines, the ithi^{th} represents the answer of the ithi^{th} query.

6 3
ABABBA
1 1 3 3 4
2 2
2 1
6 4
3
3
1