sealevel

Problem Description

Cats like to sit in high places. It is not uncommon to see cats climbing trees or furniture in order to lie on the top-most area within their feline reach. Rar the Cat is no exception. However, he does not know how high is one area relative to another.

Height is measured in centimetres (cm) above sea level and Rar the Cat does not know the absolute height of any place. However, he knows that area B_i will be higher than area A_i by H_i centimetres because he needs to jump H_i to get from area A_i to B_i. There will be N areas in total with N-1 such descriptions. Areas are labelled from 1 to N and 0 < A, B ≤ N where A ≠ B. Also, all H_i will satisfy the following range 0 ≤ H_i ≤ 10⁶.

Rar the Cat also has Q queries, each consisting 2 integers X and Y. He wants to know the height of area Y with respect to area X. Do note that 0 < X, Y ≤ N but X can be equal to Y. In the event that area Y is lower than area X, please output a negative number. Otherwise, output a positive number.

It is guaranteed that the relative heights of all pairs of areas can be computed from the data provided in the input. To be precise, the graph provided will be connected and has N-1 edges connecting N nodes in total.

Input

The first line of input will contain 1 integer, N.

The following N-1 lines of input will contain 3 integers each, with the i^th line containing A_i, B_i and H_i.

The next line will contain a single integer, Q.

The following Q lines will contain 2 integers each, X and Y.

Output

For each line of queries, you are supposed to output the relative heights of area Y compared to area X, in centimetres, one line per query.

Subtasks

For all subtasks, Q ≤ 100000.

Subtask 1 (7%): 0 < N ≤ 500.

Subtask 2 (27%): 0 < N ≤ 2000. No further restrictions.

Subtask 3 (19%): 0 < N ≤ 100000. However, for each description, A = B-1 and the descriptions will be provided in increasing order of A. Refer to Sample Input 1 for more clarity.

Subtask 4 (47%): 0 < N ≤ 100000. No further restrictions.

Subtask 5 (0%): Sample Testcases

Sample Input 1

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

Sample Output 1

0
1
3
-3
10
-10
-7
7

Note for Sample Testcase 1

The input for subtask 2 will be similar in structure to sample testcase 1.

Sample Input 2

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

Sample Output 2

-1
-15
4