Distance Queries on a Tree

You are given a tree with \(N\) cities numbered from 1 to \(N\) connected by \(N-1\) roads. Each road has an associated positive length. It is guaranteed that the tree is structured in such a way that for every query one of the two queried cities lies on the unique path from the root (city 1) to the other city.

For each query, you are asked to compute the distance between two cities \(u\) and \(v\). Since the tree is connected and weighted, the distance can be computed using the precomputed distances from city 1. In particular, if \(d(x)\) denotes the distance from city 1 to city \(x\) along the unique path, then the distance between \(u\) and \(v\) is given by:

[ D(u,v)=|d(u)-d(v)| ]

You are to process the tree and answer all queries.

inputFormat

The input is read from standard input (stdin) and has the following format:

1. An integer \(N\) representing the number of cities.
2. \(N-1\) lines follow, each containing three integers \(a\), \(b\), and \(l\), indicating there is a road connecting cities \(a\) and \(b\) with length \(l\).
3. An integer \(Q\) representing the number of queries.
4. \(Q\) lines follow, each containing two integers \(u\) and \(v\) representing a query to compute the distance between city \(u\) and city \(v\).

outputFormat

For each query, output the distance between the two cities on a separate line to standard output (stdout).

## sample

5
1 2 5
2 3 3
2 4 6
4 5 2
3
1 3
4 5
2 5

8
2
8

</p>