Background

此题没有背景~

Description

有n个节点的一棵树，每个边上带有边权，现有Q组询问，每组询问有两个数A、B，其中A,B是树上的不同的两个点，请你求出A-B路径上的权值最小值和最大值。

Format

Input

第一行为n (1<=n<=100000)接下来的n-1行，每行3个数：x,y,z，表示x和y有一条边，权值为z (1<=z<=1000000)接下来一个整数Q (1<=Q<=100000)表示Q次询问对Q行，每行两个整数A,B 表示询问A-B路径上的最小值和最大值。

Output

对每个询问，输出A-B路径上的权值最小值和最大值，中间用空格隔开。

Sample 1

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

Limitation

1s, 1024KiB for each test case.