SOLVE

LATER

Velma and Queries

/

The "Mystery Incorporated" once went for an investigation. Since Scooby and Shaggy always create havoc during investigation, Velma decided to give them a question so as to keep them busy.

Velma gave them a tree consisting of ** N** nodes, rooted at **node 1** with a number in each node, and asked them several queries. Each query was of the form **u l** and they had to find the sum of values of all nodes situated at a depth **l** and were in the subtree of **u**.

Since Scooby and Shaggy are dumb, they need your help in solving this problem.

The first line of each test case will contain two integers

The second line of each test case will contain

The next

The next

- \( 1 \leq T \leq 5, 1 \leq N, Q \leq 1000, \ 1 \leq a_i \leq 10^6 \) in 35% of test cases.
- \( 1 \leq T \leq 10, 1 \leq N, Q \leq 10^5, \ 1 \leq a_i \leq 10^6 \) in 65% of test cases.

Explanation

The tree in the test case looks like this.

The depths of nodes are:

- Nodes at depth 1:
**1** - Nodes at depth 2:
**2, 4** - Nodes at depth 3:
**3, 5 and 6**

For the 2^{nd} query , there are 3 nodes (3, 5, 6) at level 3 which are also in subtree of 1. So the answer would be 3+5+6 = 14.

For the 3^{rd} query, there is only 1 node (1) which is at level 1, but it is not in the subtree of 2. So the answer would be 0.

Time Limit:
2.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Initializing Code Editor...