You are given a tree of vertices. Each vertex contains an integer. Vertex 1 is the root of the tree, each of the remaining vertices has a parent in the tree. A vertex is connected with its parent by an edge. The parent of vertex i is vertex . The parent index is always less than the index of the vertex (i.e., ).
We say that vertex is in the sub-tree of vertex , if we can get from to , moving from the vertex to the parent. In particular, vertex is in its sub-tree.
You will be given queries, the -th of which consists of two numbers: and . You need to find out how many of vertices of sub-tree consists value greater than or equal to , that means , where vertex is in the sub-tree of vertex .
The first line contains two integers and (), the number of nodes in the tree and queries, respectively.
The following line contains integers , , ..., (), the parents of vertices from the second to the -th.
The next line contains n integers, the -th of these integers () is written on vertex .
The next lines describe the queries, the -th line contains two numbers () and (), the vertex and the depth that appear in the -th query.
For each query, print the number of vertices of sub-tree consists value greater than or equal to .
Input | Output |
---|---|
3 2 1 2 5 6 7 1 3 1 6 | 3 2 |