The traffic network in a country consists of N cities (labeled with integers from 1 to N) and N1 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 N1 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
