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 L−1 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 N−1 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!
- 1≤N,Q≤3×105
- 1≤Xi,Li≤N
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