UNRDA Mentor Pair Queries

The United Nations Regional Development Agency (UNRDA) has a well‐structured organization. It employs N members numbered from $1$ to $N$, with member $1$ (the chairman) being the most senior. Each member is assigned to one of $R$ regions (numbered from $1$ to $R$). Except for the chairman, every member has a direct mentor, and a mentor always has a lower number (i.e. higher seniority) than the person he mentors.

We say member $A$ is a mentor of member $B$ if and only if either $A$ is the direct mentor of $B$ or $A$ is a mentor of the direct mentor of $B$. Evidently, the chairman is the mentor of every other member and there are no two members who are mentors of each other.

Due to allegations of regional bias in UNRDA's structure, a computer system is required. Given the direct mentor relationships and regions assigned to each member, the system must answer queries of the following form online: Given two regions $r_1$ and $r_2$, determine how many ordered pairs $(e_1, e_2)$ exist such that member $e_1$ belongs to region $r_1$, member $e_2$ belongs to region $r_2$, and $e_1$ is a mentor (direct or indirect) of $e_2$.

Task: Write a program that, after reading the members' regions and their direct mentor relationships, answers $Q$ online queries. Each query consists of two parameters $r_1$ and $r_2$, and the result is an integer representing the number of valid $(e_1, e_2)$ pairs.

Note: The online queries will be handled in an interactive format. For the purpose of this problem, you may assume that all input is provided at once.

inputFormat

The input begins with three integers $N$, $R$, and $Q$, where $N$ is the number of members, $R$ is the number of regions, and $Q$ is the number of queries.

The next line contains $N$ integers, where the $i$-th integer denotes the region of member $i$ (for $1 \le i \le N$).

Then follow $N-1$ lines. The $i$-th of these lines (for $i$ from $2$ to $N$) contains a single integer representing the direct mentor of member $i$. (Member $1$ is the chairman and has no mentor.)

Finally, there are $Q$ lines, each containing two integers $r_1$ and $r_2$, representing a query.

outputFormat

For each query, output a single integer on a new line: the number of ordered pairs $(e_1, e_2)$ such that member $e_1$ is from region $r_1$, member $e_2$ is from region $r_2$, and $e_1$ is a mentor (direct or indirect) of $e_2$.

sample

6 3 3
1 2 1 3 2 1
1
1
2
2
3
1 1
2 1
1 2

3
0
2