Problem Description

There is a tree with $ N $ vertices, numbered from $ 1 $ to $ N $, and $ N-1 $ edges, numbered from $ 1 $ to $ N-1 $. Edge $ i $ connects vertices $ A_i $ and $ B_i $.

$ M $ people, numbered from $ 1 $ to $ M $, will move on this tree. Person $ i $ starts at vertex $ V_i $ and performs the following operation exactly $ L_i $ times:

• Choose any edge connected to the current vertex, move to the adjacent vertex through this edge. If the edge number is $ x $, gain $ C_x $ points.

For each $ i $, find the maximum total score person $ i $ can obtain after $ L_i $ operations.

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_1 $ $ B_1 $ $ C_1 $ $ A_2 $ $ B_2 $ $ C_2 $ $\vdots$ $ A_{N-1} $ $ B_{N-1} $ $ C_{N-1} $ $ M $ $ V_1 $ $ L_1 $ $ V_2 $ $ L_2 $ $\vdots$ $ V_M $ $ L_M $

Output Format

Output $ M $ lines. The $ i $-th line should contain the maximum total score person $ i $ can obtain after $ L_i $ operations.

Sample Input and Output

Sample Input #1

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

Sample Output #1

10
5
19

Sample Input #2

12
9 10 13
5 8 78
1 7 96
3 5 56
7 9 99
4 12 36
7 12 45
7 11 37
8 9 69
2 7 60
6 7 71
10
9 7
8 1
1 2
11 18
1 18
3 5
9 17
9 13
9 16
5 5

Sample Output #2

693
78
195
1720
1779
401
1683
1287
1584
444

Notes/Hints

Constraints

• $2 \leq N \leq 10^5$
• $1 \leq A_i < B_i \leq N$
• $1 \leq C_i \leq 10^9$
• $1 \leq M \leq 10^5$
• $1 \leq V_i \leq N$
• $1 \leq L_i \leq 10^9$
• The graph given in the input is a tree.
• All values in the input are integers.

Sample Explanation 1

Person $ 1 $ can maximize the total score in 3 operations as follows:
- Move from vertex $ 5 $ to vertex $ 3 $ using edge $ 4 $, gaining $ 2 $ points.
- Move from vertex $ 3 $ to vertex $ 4 $ using edge $ 3 $, gaining $ 4 $ points.
- Move from vertex $ 4 $ to vertex $ 3 $ using edge $ 3 $, gaining $ 4 $ points.

Person $ 2 $ can maximize the total score in 1 operation as follows:
- Move from vertex $ 2 $ to vertex $ 1 $ using edge $ 1 $, gaining $ 5 $ points.

Person $ 3 $ can maximize the total score in 5 operations as follows:
- Move from vertex $ 5 $ to vertex $ 3 $ using edge $ 4 $, gaining $ 2 $ points.
- Move from vertex $ 3 $ to vertex $ 2 $ using edge $ 2 $, gaining $ 2 $ points.
- Move from vertex $ 2 $ to vertex $ 1 $ using edge $ 1 $, gaining $ 5 $ points.
- Move from vertex $ 1 $ to vertex $ 2 $ using edge $ 1 $, gaining $ 5 $ points.
- Move from vertex $ 2 $ to vertex $ 1 $ using edge $ 1 $, gaining $ 5 $ points.

见题面 Input 部分

见题面 Output 部分