Description

Finally, the students finished the pudding. Kaede, who loves pudding the most, started thinking: how tasty is this pudding?

How tasty a pudding is depends on the flavor-changing ingredients inside. Different ingredients have different colors and tastiness values.

There are $n$ kinds of flavoring ingredients in the pudding, connected by $n-1$ links. The first ingredient is at the top, which is the root of this tree.

Now, Kaede defines that the tastiness of the pudding depends on two given values $u, k$. This tastiness is defined as follows: let $v$ be the $k$-th ancestor of ingredient $u$. Consider all $k$-th level children of ingredient $v$, and among them, take those $k$-th level children whose color is the same as the color of ingredient $v$. The answer is the sum of the tastiness values of these selected nodes. It can be seen that when $u$ or $k$ changes, in general the tastiness value also changes. Therefore, there are $q$ queries to ask you.

In particular, if ingredient $u$ does not have a $k$-th ancestor, output $0$ directly.

Input Format

The first line contains two integers $n, q$, meaning there are $n$ ingredients and $q$ queries.

The second line contains $n$ integers. The $i$-th integer represents the color of ingredient $i$, $color_i$.

The third line contains $n$ integers. The $i$-th integer represents the tastiness value of ingredient $i$, $d_i$.

The fourth line contains $n-1$ integers. The $i$-th integer represents the parent node of the ingredient $i+1$, $fa_i$.

The next $q$ lines each contain two integers $u, k$, representing a query.

Output Format

There are $q$ lines, each containing one integer, representing the answer to the query.

3 1
1 1 1
1 2 3
1 1
2 1

5

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

0
6
0

Hint

Sample Explanation #1

The $1$-st ancestor of ingredient $2$ is ingredient $1$. The $1$-st level children of ingredient $1$ are ingredients $2$ and $3$. The colors of ingredients $2$ and $3$ are both the same as the color of ingredient $1$, so the sum of tastiness values is $2 + 3 = 5$.

Constraints

This problem uses bundled testdata.

• Subtask 1 (30 points): Eggs are scarce, the pudding is small: $n \leq 10^3$, $q \leq 10^4$.
• Subtask 2 (20 points): The ingredients form a chain: $n \leq 5 \times 10^5$, $q \leq 10^5$, $color_i \leq 10^2$.
• Subtask 3 (50 points): No special restrictions on the testdata.

For $100\%$ of the testdata, $1 \leq n, q, color_i \leq 5 \times 10^5$, $1 \leq d_i \leq 10^5$.

Hint

The time limit for the test points in Subtask 2 and Subtask 3 is 2S.

Translated by ChatGPT 5