Given a tree with edge weights of $1$ and a constant $C$, nodes are represented by integers from $1$ to $n$.

Define $dist(a,b)$ as the distance between nodes $a$ and $b$ in the tree, which is the sum of edge weights on the simple path between $a$ and $b$. Specifically, $dist(a,a) = 0$.

For each query, you are given an interval $[l,r]$. Calculate the number of C-blocks, defined as follows:

For any two nodes $a,b$, $a$ and $b$ are C-connected if and only if there exists a sequence of nodes $\{v_i\}$ of length $t$ such that:

1. $v_1=a$
2. $v_t=b$
3. For any $1\le i\le t-1$, $dist(v_i,v_{i+1})\le C$
4. For any $1\le i\le t$, $l\le v_i\le r$

A "C-block" is defined as a set of nodes $S$ such that:

1. For any $a \in S$ and $b \notin S$, $a$ and $b$ are not C-connected.
2. For any $a,b \in S$, $a$ and $b$ are C-connected.
3. For any $a \in S$, $l\le a \le r$.

Input

The first line contains three integers $n$, $m$, and $C$, representing the number of nodes in the tree, the number of queries, and the constant $C$, respectively.

The second line contains $n-1$ integers $p_2, p_3, \dots, p_n$, where for each integer $i$ such that $2 \le i\le n$, there is an undirected edge between $i$ and $p_i$.

It is guaranteed that the input forms a tree.

The following $m$ lines each contain two integers $l$ and $r$, representing the query interval $[l,r]$. It is guaranteed that $l \le r$.

It is guaranteed that $1 \le n\le 3\cdot 10^5$ and $1 \le m\le 6\cdot 10^5$.

Output

Output $m$ lines, each containing a single integer representing the answer to the corresponding query.

Examples

Input 1

10 9 2
1 1 1 2 3 4 1 1 1
1 3
2 4
3 5
4 6
5 7
6 8
7 9
8 10
5 5

Output 1

1
1
2
3
3
3
2
1
1

Subtasks

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

This problem has multiple subtasks. Each subtask may contain multiple test cases. You only receive points for a subtask if you pass all test cases within that subtask.

The test cases for each subtask satisfy specific constraints as shown in the table below:

The meanings of Property 1 and Property 2 are as follows:

Property 1: There exists a node $w$ such that $dist(1,w)=n-1$.

Property 2: $n=m$, and the $i$-th query is $l=1, r=i$.