C. And yet it moves
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Isidra likes to travel between galaxies in her free time. After years of study, the "Facultad de Fomento del Turismo" provides a map that includes the distances between galaxies. Perhaps because the funds dedicated to research were not enough to obtain more data, or perhaps because of fear of finding inconsistencies in the results and because no one really understands the laws of physics, the map provided is a bit special, in such a way that between any two galaxies, there is only one way to measure the distance between them.

Isidra is one of those people who say that the journey is the actual path and not the destination, so the longer the journey, the more she enjoys it. She is also aware that as time passes, galaxies always move further away from each other. To make things easier, the map provides, on one hand, the initial distance between galaxies, and on the other hand, how much that distance will increase with each passing year. Isidra is very inquisitive, so she would like to know for two different galaxies, what is the minimum whole number of years that must pass for these two galaxies to be at a distance greater than or equal to whatever value she wants.

More formally, $$$n$$$ galaxies and $$$n-1$$$ distance measures between pairs of galaxies are given. The measurement $$$i$$$ between galaxies $$$u_i$$$ and $$$v_i$$$ consists of two integers $$$a_i, b_i$$$, such that after $$$t$$$ years, the distance between $$$u_i$$$ and $$$v_i$$$ is $$$d_i = a_i$$$ + $$$t \cdot b_i$$$. A question from Isidra is of the form $$$(u, v, w)$$$, which means "what is the minimum integer number of years that must pass for the distance between $$$u$$$ and $$$v$$$ to be greater than or equal to $$$w$$$?"

Of course, Isidra won't be satisfied with just one question, so be prepared to answer many of them.

Input

The first line contains a single integer $$$n$$$ — the number of galaxies.

The following $$$n-1$$$ lines each include four integers $$$(u_i, v_i, a_i, b_i)$$$ — the two galaxies $$$u_i, v_i$$$ that make up the $$$i$$$-th measurement, the initial distance $$$a_i$$$ between them and the extra distance $$$b_i$$$ that they separate each year. The distances are independent of the direction in which you travel between the two galaxies.

The next line contains a single integer $$$q$$$ — the number of questions.

Next will come $$$q$$$ lines, each containing three integers $$$(u_i, v_i, w_i)$$$ — the two galaxies $$$(u_i, v_i)$$$ ($$$u_i \neq v_i$$$) for which to compute the minimum time so that the distance is greater than or equal to $$$w_i$$$.

  • $$$2 \le n \le 10^5$$$
  • $$$1 \le u_i, v_i \le n$$$
  • $$$1 \le a_i, b_i \le 10^4$$$
  • $$$1 \le q \le 10^5$$$
  • $$$1 \le w \le 10^9$$$
Output

Print $$$q$$$ integers separated by spaces, the answers to each question, in the given order. If they are already at a distance greater than or equal to that requested at the initial moment, the response will be $$$0$$$.

Example
Input
3
1 2 1 2
1 3 1 1
3
2 1 4
2 3 5
1 3 1
Output
2 1 0