Ellen is a student at RHHS who is trying to navigate her way through the school to get to her classes. She knows that most halls are going to be blocked off by large groups of aimless students, so she has devised a map of the school which only includes hallways she knows will be open. In particular, the school can be represented as a collection of classrooms numbered to with hallways between them. It is guaranteed that these hallways will never form a loop.

Because Ellen is travelling around the school a lot, she wants to know how far it is between various different locations in the school, so she can plan how long it will take to walk between them.

To help her with this, you will be given queries; for each one you must determine the distance between the two given classrooms.

#### Input Specification

The first line will contain , the number of classrooms.

The next lines will contain three space-separated integers, , , , , indicating that there is a hallway between classrooms and with length .

The next line will contain , the number of queries to be answered.

The next lines will contain two space-separated integers, and , representing a query that asks the distance between classrooms and .

For test cases worth 20 of 100 points, and .

For test cases worth an additional 20 points, .

#### Output Specification

For each query, output a single integer on its own line which is the distance between the two classrooms in the query.

#### Sample Input

```
5
0 1 3
0 3 2
0 4 7
1 2 5
4
2 0
1 4
3 1
3 4
```

#### Sample Output

```
8
10
5
9
```

## Comments

are hallways bidirectional?

This comment is hidden due to too much negative feedback. Click here to view it.

was that not an intended solution?

or did they just not want data to be huge?

Likely the latter, as their solution was

Seriously? I was halfway through solving this problem when you lowered the points. If anything, just tighten the time limit if you think it is too easy.

That's up to the problemsetter as the admins would be encroaching on their "creative license" by changing the time limit.