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 Bi will be higher than area Ai by Hi centimetres because he needs to jump Hi to get from area Ai to Bi. There will be N areas in total with N-1 such descriptions. Areas are labelled from 1 to N and 0 < A, BN where AB. Also, all Hi will satisfy the following range 0 ≤ Hi ≤ 106.

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, YN 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 ith line containing Ai, Bi and Hi.

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

Submitting .cpp to 'sealevel'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 1 Seconds
Memory Limit: 256MB
No. of ACs: 86
Your best score: 0
Source: Dunjudge Archive

Subtask Score
1 7
2 27
3 19
4 47
5 0