Given a rooted tree with vertices labeled $1, 2, \dots, n$, where for $2 \le i \le n$, $f_i$ is the parent of $i$. $a_1, \dots, a_n$ is a permutation of $1, \dots, n$.

There are $m$ queries. Each query provides $l, r$, and asks for the number of pairs $(L, R)$ such that $l \le L \le R \le r$, and for any $L \le a_x \le a_y \le R$, the lowest common ancestor $z$ of $x$ and $y$ in the tree satisfies $L \le a_z \le R$.

All values above are integers.

Input

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

The next line contains $n$ integers $a_1, \dots, a_n$.

The next $n-1$ lines contain $f_2, \dots, f_n$ in order.

The next $m$ lines each contain $l, r$ representing a query.

Output

For each query, output one line representing the answer.

Examples

Input 1

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

Output 1

1
10
1
1
1

Subtasks

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

For $100\%$ of the data, $1 \le n, m \le 2 \times 10^5$, $1 \le f_i \le i-1$, and $l \le r$.

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

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

For another $25\%$ of the data, $l=1, r=n, m=1$.

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