Description

Melo earned a lot of money by moving bricks and became the boss eventually, so he established a brick-moving mega-company, and so many people want to follow Melo and he decided to put all offices on a huge tree. There are $N$ nodes on this tree, representing N departments' offcie, and node 1 is the root of the tree, and it also is Melo's headquarters. Every node has edges that connected other node. Melo likes to interview some departments and then have a meeting with all the employees of the department. Due to the boss is generous, costs can be free if distance less than $k$, otherwise they will cost the same as the distance.

When Melo arrives at node $x$, he will ask all the employees of the department to gather at $x$. Melo will ask the secretary to count all their travel expenses. He is not good at math, so can you help him figure out the answer?

Format

Input

The first line contains an integer $N$, indicating that the tree has $N$ nodes.

The next $N-1$ lines describe the edges which connected different nodes，there are three integers $u, v, c$ denote that the distance between $u$ and $v$ is $c$.

The $N+1$ line contains a positve integer $Q$, indicating the times of Melo's query.

For the next $Q+1$ lines, each line contains two integers $x$ and $k$.

$(1 \leq N,Q \leq 2×10^5$,$1 \leq c,k \leq 10^6, 1 \leq x \leq n)$

Output

For each query, print a singe line containing one number, denoting the sum of all the nodes in the subtree of $x$ whose distance from $x$ is greater than or equal to $k$.(If no such nodes exists, the answer is 0)

Samples

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

3
2

Hint