#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## 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*by

_{i}*H*centimetres because he needs to jump

_{i}*H*to get from area

_{i}*A*to

_{i}*B*. There will be

_{i}*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*will satisfy the following range 0 ≤

_{i}*H*≤ 10

_{i}^{6}.

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*and

_{i}*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

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 7 | 20 | 1s | 256MB | Minimum |

2 | 27 | 40 | 1s | 256MB | Minimum |

3 | 19 | 10 | 1s | 256MB | Minimum |

4 | 47 | 70 | 1s | 256MB | Minimum |

5 | 0 | 2 | 1s | 256MB | Minimum |

### Judge Compile Command

g++-7 ans.cpp -o sealevel -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512