Connected Subtree Interval Query

Given a rooted tree with n vertices numbered from 1,2,…,n, where for every vertex i (2 ≤ i ≤ n) its parent is given by f_i. You are also given a permutation a₁,a₂,…,a_n of the numbers 1,2,…,n.

We say that an interval of integers [L,R] (with 1 ≤ L ≤ R ≤ n) is good if the set of vertices

forms a connected subtree of the given tree. Equivalently, if we denote by pos[i] the vertex with a_pos[i] = i (i.e. the inverse permutation), then [L,R] is good if and only if the set

forms a connected subtree. This is equivalent to the following condition: if we take the unique simple path between pos[L] and pos[R] in the tree, and let (m) and (M) be the minimum and maximum values of a[u] over all vertices u on this path, then we must have

[ m = L \quad\text{and}\quad M = R. ]

You are given m queries. Each query gives two integers l and r (1 ≤ l ≤ r ≤ n). For each query, compute the number of good intervals [L,R] such that l ≤ L ≤ R ≤ r.

All numbers in the input are integers.

inputFormat

The first line contains two integers n and m — the number of vertices and the number of queries, respectively.

The second line contains n-1 integers: f₂, f₃, …, f_n where f_i is the parent of vertex i (the tree is rooted at vertex 1).

The third line contains n distinct integers a₁, a₂, …, a_n — a permutation of the numbers 1,2,…,n.

Then follow m lines, each containing two integers l and r representing a query.

outputFormat

For each query, output a single integer — the number of good intervals [L,R] with l ≤ L ≤ R ≤ r that satisfy the property described above.

sample

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

9
3
3

</p>