F. Good Friend
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

$$$Abdullah$$$ and his friend $$$Kifah$$$ live in a real country called $$$BP$$$, which has $$$n$$$ cities that can be described as a weighted tree rooted at node $$$1$$$.

$$$kifah$$$ wants to buy some presents for his girlfriend but unfortunately he doesn't have any money, so he will borrow some money from his friend $$$Abdullah$$$.

$$$Abdullah$$$ is a good friend, so he will help $$$Kifah$$$.

Abdullah works as a TAXI driver. For a ride from city $$$a$$$ to city $$$b$$$ (note that city $$$b$$$ must be in the subtree of the $$$a$$$, more formally the city $$$a$$$ must lie on the simple path between city $$$1$$$ and city $$$b$$$), $$$Abdullah$$$ earns an amount of money equal to the sum of weights in the simple path between $$$a$$$ and $$$b$$$ , and he spends hours equal to the number of edges in the simple path between $$$a$$$ and $$$b$$$.

$$$Kifah$$$ loves his girlfriend so much and wants to buy her $$$q$$$ presents.

$$$Abdullah$$$ will give you the construction of the country and then for each present he will tell you the city $$$city_i$$$ that he is currently located in and the price $$$p_i$$$ of the present that $$$Kifah$$$ wants to buy. Can you tell him the minimum possible number of hours required to make money more than or equal to $$$p_i$$$. If it's impossible to earn that amount of money just print $$$-1$$$.

Input

The first line contains an integer $$$n (1 \le n \le 10^5)$$$, the number of the cities in $$$BP$$$.

The next $$$n-1$$$ lines describe the roads. The $$$i_{th}$$$ line contains three integers $$$u_i$$$, $$$v_i$$$ and $$$w_i$$$ $$$(1 \le u_i,v_i \le n, u_i \neq v_i, 1 \le w_i \le 10^9 )$$$, meaning that there is an edge between the nodes $$$u_i$$$ and $$$v_i$$$ with weight $$$w_i$$$.

The next line contains a single integer $$$q$$$ $$$(1 \le$$$ $$$q \le 10^5)$$$, the number of presents that $$$Kifah$$$ wants to buy for his girlfriend.

For the following $$$q$$$ lines, the $$$i_{th}$$$ line contains two integers $$$city_i, p_i$$$ $$$(1 \le city_i \le n, 1 \le p_i \le 10^{18})$$$ meaning that $$$Abdullah$$$ will start from $$$city_i$$$ and wants to earn an amount of money more than or equal to $$$p_i$$$.

Output

For each present, print the minimum possible number of hours required to make money more than or equal to $$$p_i$$$ if $$$Abdullah$$$ started the ride from $$$city_i$$$, or if it's impossible to earn that amount of money, just print $$$-1$$$.

Example
Input
5
1 2 3
2 3 4
2 4 2
3 5 6
3
1 6
2 11
5 2
Output
2
-1
-1
Note

To buy the first present, $$$Abdullah$$$ can go from city $$$1$$$ to city $$$3$$$ spending $$$2$$$ hours, and earning an amount of money equal to $$$7$$$ which is greater than $$$6$$$.

For the second present, the maximum amount of money $$$Abdullah$$$ can earn is $$$10$$$ by having a ride to the city $$$5$$$, $$$10$$$ is lower than $$$11$$$, so the answer is $$$-1$$$.

For the third present, $$$Abdullah$$$ can't go to any city (because there are no cities in the subtree of the city $$$5$$$), so the answer is $$$-1$$$.