Given a rooted tree with $n$ nodes, define $N(w, d)$ (where $w$ is a vertex of the tree and $d$ is a non-negative integer) as the set of nodes in the subtree rooted at $w$ whose distance to $w$ is at most $d$.

There are $m$ queries. For each query, given $w$ and $d$, calculate the size of the set $\{N(w', d') \mid N(w', d') \subseteq N(w, d)\}$.

Input

The first line contains two integers $n$ and $m$.

The second line contains $n-1$ integers $f_2, \dots, f_n$, where $f_i$ denotes the parent of node $i$.

The next $m$ lines each contain two integers $w$ and $d$, representing a query.

Output

Output $m$ lines, each containing the answer to the corresponding query.

Examples

Input 1

5 4
1 2 2 3
3 1
3 0
5 0
1 2

Output 1

3
1
1
7

Subtasks

Idea: nzhtl1477, Solution: ccz181078, Code: ccz181078, Data: ccz181078

For $100\%$ of the data, $1\le n, m\le 10^6$, $1\le f_i < i$, $1\le w\le n$, $0\le d\le n-1$.

For $25\%$ of the data, $n, m\le 100$.

For another $25\%$ of the data, $n, m\le 5000$.

For another $25\%$ of the data, $n, m\le 2\times 10^5$.

For the remaining $25\%$ of the data, there are no additional constraints.