Tree Queries

You are given a tree of $n$ vertices. Each vertex contains an integer. Vertex 1 is the root of the tree, each of the $n-1$ 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 $p_i$. The parent index is always less than the index of the vertex (i.e., $p_i < i$).

We say that vertex $u$ is in the sub-tree of vertex $v$, if we can get from $u$ to $v$, moving from the vertex to the parent. In particular, vertex $v$ is in its sub-tree.

You will be given $m$ queries, the $i$-th of which consists of two numbers: $v$ and $x$. You need to find out how many of vertices of sub-tree $v$ consists value greater than or equal to $x$, that means $a_u ≥ x$, where vertex $u$ is in the sub-tree of vertex $v$.

Input

The first line contains two integers $n$ and $m$ ($1 ≤ n, m ≤ 5 × 10^5$), the number of nodes in the tree and queries, respectively.

The following line contains $n-1$ integers $p_2$, $p_3$, ..., $p_n$ ($1 ≤ p_i < i$), the parents of vertices from the second to the $n$-th.

The next line contains n integers, the $i$-th of these integers $a_i$ ($1 ≤ a_i ≤ 10^9$) is written on vertex $i$.

The next $m$ lines describe the queries, the $i$-th line contains two numbers $v$ ($1 ≤ v ≤ n$) and $x$ ($1 ≤ x ≤ 10^9$), the vertex and the depth that appear in the $i$-th query.

Output

For each query, print the number of vertices of sub-tree $v$ consists value greater than or equal to $x$.

Sample

Input	Output
3 2 1 2 5 6 7 1 3 1 6	3 2