QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 2048 MB
[0]

# 9712. Loli, Yen-Jen, and a cool problem

Statistics

Yen-Jen loves loli very much!!!

Now, he is solving a problem with a cute, cat-eared loli. 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 N vertices(vertices are numbered from 1 to N) whose root is 1. In every node, there's an uppercase letter on it.

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

  • select a start node X
  • go to the parent node L1 times
  • whenever goes to a node, append the corresponding English letter to the end of the string

Now there are Q queries, in the ith query, a start node Xi is given. Please count the number of starting node Y(include Xi), such that Y can generate the same string as Xi.

Input

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

In the next line, a string S is given, the ith character means the English letter on the ith node.

Then, there are N1 integers in one line, the ith integer is the parent of node i+1.

Then, there are Q lines, the ith line represents the ith query. In each line, Xi,Li is given, which is mentioned in the description.

It is guaranteed that the testcase is valid!

  • 1N,Q3×105
  • 1Xi,LiN

Output

Output Q lines, the ith represents the ansewr of the ith query.

Sample Input

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

Sample Output

3
3
1