Giải bài trực tuyến

The traffic network in a country consists of N cities (labeled with integers from 1 to N) and N-1 roads connecting the cities. There is a unique path between each pair of different cities, and we know the exact length of each road. Write a program that will, for each of the K given pairs of cities, find the length of the shortest and the length of the longest road on the path between the two cities.

Input

• The first line of input contains an integer N, 2 ≤ N ≤ 100 000.
• Each of the following N-1 lines contains three integers A, B and C meaning that there is a road of length C between city A and city B. The length of each road will be a positive integer less than or equal to 1 000 000. The next line contains an integer K, 1 ≤ K ≤ 100 000.
• Each of the following K lines contains two different integers D and E – the labels of the two cities constituting one query.

Output

Each of the K lines of output should contain two integers – the lengths from the task description for the corresponding pair of the cities.

Example

Input
1 6 5 100
25
50
50
10
20
23

Output
100 200
50 150
50 100

Input
7
3 6 4
1 7 1
1 3 2
1 2 6
2 5 4
2 4 4
5
6 4
7 6
1 2
1 3
3 5

Output
2 6
1 4
6 6
2 2
2 6

Input
9
1 2 2
2 3 1
3 4 5
2 7 4
1 5 3
5 6 1
5 9 2
1 8 3
5
6 9
7 8
9 4
1 2
7 3

Output
1 2
2 4
1 5
2 2
1 4