Problem Statement

Penguinman loves playing with trees.

There is a tree with $N$ vertices. The $i$-th edge bidirectionally connects vertex $u_i$ and vertex $v_i$, and its length is $w_i$. You are given $Q$ queries of the following form; process them in order.

• Among the vertex sequences, in which elements may repeat, that start at vertex $x$, end at vertex $y$, and satisfy both of the following conditions, find and output the length of the one with the $2$-nd shortest length. If no such vertex sequence exists, output $-1$ instead.

  1. The $i$-th vertex and the $i+1$-th vertex are directly connected by an edge $(1≤i≤($size of the vertex sequence$-1))$.
  2. Among the edges connecting the $i$-th vertex and the $i+1$-th vertex, the same edge appears at most $2$ times.

Also, vertex sequences that differ as sequences are treated as distinct even if their lengths are equal.

Input

$N$
$u_1\ v_1\ w_i$
:
$u_{N-1}\ v_{N-1}\ w_{N-1}$
$Q$
$x_1\ y_1$
$︙$
$x_Q\ y_Q$

For convenience, $x,y$ in the $i$-th query are denoted by $x_i,y_i$, respectively.

It is guaranteed that the input satisfies the following constraints.

• $2≤N≤10^5$
• $1≤Q≤10^5$
• $1≤u_i,v_i≤N(1≤i≤N-1)$
• $1≤w_i≤10^9(1≤i≤N-1)$
• $1≤x_i,y_i≤N(1≤i≤Q)$
• $u_i≠v_i(1≤i≤N-1)$
• $x_i≠y_i(1≤i≤Q)$
• The given graph is a tree.
• All input values are integers.

Output

On the $i$-th line, output the answer to the $i$-th query.

Sample

3
1 2 3
2 3 4
2
1 2
1 3

11
-1

5
1 4 10
2 3 100
1 2 38
1 5 2
4
1 2
2 3
3 4
1 4

42
176
152
14

6
1 3 19
1 2 20
1 4 1
5 1 10
4 6 8
5
1 2
3 4
5 3
6 2
3 1

22
36
31
49
21