There are ~N~ nodes with IDs from ~1~ to ~N~. All nodes, with the exception of Node ~1~, has a parent node with an ID less than itself. Each node has a value. The ~i^{\text{th}}~ node has a value of ~V_i~.

A ~k^{\text{th}}~ ancestor of a node is defined as follows:

• If ~k = 1~, the parent of the node
• If ~k > 1~, the parent of the ~(k - 1)^{\text{th}}~ ancestor of the node

Two nodes are considered ~k^{\text{th}}~ cousins if and only if their ~k^{\text{th}}~ ancestors both exist and are the same node.

A node ~a~'s ~k^{\text{th}}~ cousins is the set of all nodes ~b~ for which ~a~ and ~b~ are ~k^{\text{th}}~ cousins.

Answer ~Q~ queries, each asking: "Given ~n~ and ~k~, what is the sum of the values ~k^{\text{th}}~ cousins of ~n~?"

Constraints

~1 \leq N, Q \leq 200~ ~000~

~1 \leq V_i \leq 10~ ~000~

~1 \leq n, k \leq N~

Input Specification

The first line contains ~N~ and ~Q~.

The second line contains ~N~ integers, the ~i^{\text{th}}~ integer being ~V_i~.

The third line contains ~N - 1~ integers, the parents of Node ~2~ to Node ~N~.

The next ~Q~ lines contain two integers each, ~n~ and ~k~.

Output Specification

Print ~Q~ lines, the answers to the ~Q~ queries, in the order that they are given.

Sample Input

9 2
1 2 4 8 16 32 64 128 256
1 1 3 3 3 4 6 6
6 1
8 2

Sample Output

24
320