I have gone over the scenarios in my head,

and there are 6.96969 billion outcomes, and only one of them -

- do I win.

source

---

Dream abstracts the fabric of spacetime as a directed rooted tree (arborescence) with ~N~ nodes (numbered ~1~ through ~N~). Node ~1~ is the root and for each ~i~ ~(1 \le i \le N-1)~, the parent of node ~i+1~ is ~f_i~. All edges of this tree are directed away from the root.

Then, Dream employs a magical superpower and adds ~M~ directed edges to this tree in such a way that the resulting directed graph remains acyclic (a DAG).

Let's call a node of this DAG an event and further call a simple path on this DAG an era. Dream considers a pair of events ~(i, j)~ to be plausible if there is an era whose first event is ~i~ and last event is ~j~.

Dream now wants you to answer ~Q~ queries. In each query, he gives you two positive integers ~l~ and ~r~, where ~l \le r~, and he wishes to know the number of plausible pairs of events ~(i, j)~ such that ~l \le i, j \le r~.

Constraints

~2 \le N \le 10^5~

~0 \le M \le 10^5~

~1 \le Q \le 10^6~

The given tree and ~M~ extra edges form a DAG.

Subtask 1 [1%]

The tree is a line graph.

Subtask 2 [11%]

~N, M, Q \le 10^3~

Subtask 3 [7%]

~M \le 5~

Subtask 4 [23%]

~N, M, Q \le 5 \times 10^4~

Subtask 5 [17%]

~Q \le 10^5~

Subtask 6 [41%]

No additional constraints.

Input Specification

The first line of the input contains two integers ~N~ and ~M~.

The second line contains ~N-1~ integers ~f_1, f_2, \dots, f_{N-1}~.

~M~ lines follow. Each of these lines contains two integers ~u~ and ~v~ describing an additional edge from node ~u~ to node ~v~.

The following line contains a single integer ~Q~.

~Q~ lines follow. Each of these lines contains two integers ~l~ and ~r~ describing a query.

Output Specification

For each query, print a single line containing one integer — the number of plausible pairs ~(i, j)~ such that ~l \le i, j \le r~.

Sample Input

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

Sample Output

6
5
27