Pudding's Deliciousness Evaluation

In this problem, you are given a pudding that is prepared with n ingredients arranged in a tree structure. The first ingredient is the root (top ingredient) and the remaining n-1 ingredients are connected to form a tree. Each ingredient has a color and a deliciousness value.

You will be given q queries. For each query, with parameters u and k, you need to compute the following:

1. Find the k-th ancestor of ingredient u. The parent is considered the 1st-level ancestor, the parent's parent is the 2nd-level ancestor, and so on. If ingredient u does not have a k-th ancestor, output 0.
2. Let v be the k-th ancestor of u. Find all ingredients which are exactly k levels below v (i.e. the k-th level children of v) and have the same color as ingredient v.
3. The answer to the query is the sum of deliciousness values of these ingredients.

Note: If u does not have a k-th ancestor, simply output 0.

inputFormat

The first line contains two integers n and q — the number of ingredients and the number of queries.

The second line contains n integers representing the colors of the ingredients. (1-indexed)

The third line contains n integers representing the deliciousness values of the ingredients.

The fourth line contains n-1 integers. For i = 2 to n, the i-1-th integer is the index of the parent of ingredient i (thus forming a tree with ingredient 1 as the root). If n = 1, this line will be empty.

Each of the next q lines contains two integers u and k, representing a query.

outputFormat

For each query, output a single integer — the sum of deliciousness values of all the k-level children of the k-th ancestor of ingredient u which have the same color as that ancestor. If the k-th ancestor does not exist, output 0.

sample

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

7
8
0