Problem Background

Kayano Kaede has devised a plan to assassinate the teacher using a pudding. They used the remaining eggs to make a pudding and added some flavor-changing ingredients wrapped in rice paper for appearance and taste. These ingredients are arranged in a tree-like structure from top to bottom. At the bottom of the pudding, there are hidden bombs that will detonate when the teacher eats that part.

Problem Description

Finally, the students have finished making the pudding. Kayano, who loves pudding the most, starts to wonder, how delicious is this pudding?

The deliciousness of a pudding depends on the flavor-changing ingredients inside. Different ingredients have different colors and deliciousness values.

There are $n$ types of flavor ingredients in the pudding, connected by $n-1$ links, with the first ingredient at the top, acting as the root of this tree.

Now, Kayano has determined that the deliciousness of the pudding is related to specified values $u$ and $k$. The deliciousness is the sum of the deliciousness values of all $k$-th level children of the $k$-th level ancestor $v$ of the $u$-th ingredient, where these children have the same color as $v$. It can be observed that different $u$ or $k$ values generally result in different deliciousness values. Therefore, there are $q$ questions to ask you.

Specifically, if the $u$-th ingredient does not have a $k$-th level ancestor, output $0$ directly.

Input Format

The first line contains two integers $n$ and $q$, representing the number of ingredients and the number of queries, respectively.

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

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

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

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

Output Format

There are $q$ lines, each containing one integer, representing the result of the query.

Sample Input and Output

Sample Input #1

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

Sample Output #1

5

Sample Input #2

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

Sample Output #2

0
6
0

Notes/Hints

Sample Explanation #1

The 1-level ancestor of ingredient 2 is ingredient 1. The 1-level children of ingredient 1 are ingredients 2 and 3. Both ingredients 2 and 3 have the same color as ingredient 1, so the sum of their deliciousness values is $2 + 3 = 5$.

Data Range

This problem uses batched testing.

• Subtask 1 (30 points): Lack of eggs, small pudding: $n \leq 10^3$, $q \leq 10^4$.
• Subtask 2 (20 points): 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.

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

Hint

The time limit for the second subtask and the third subtask is 2 seconds.

见题面 Input 部分

见题面 Output 部分