管道中的奇诺比奥

蘑菇王国里有 $N$ 只奇诺比奥，他们被要求在各自的房子之间建造一个管道网络，以便在整个王国中快速旅行。每只奇诺比奥 $i$（编号从 $1$ 到 $N$）会选择另一只奇诺比奥 $j \neq i$，并建造一条双向连接他们房子的管道；这条管道双向通行都需要花费 $t_i$ 的时间。奇诺比奥队长希望所有奇诺比奥都能足够快地互相到达，因此他可能会在不同的房子对之间建造一些额外的管道。

在所有管道建成后，奇诺比奥队长想要检查奇诺比奥们在房子之间旅行的速度，因此他向你提出了 $Q$ 个询问，每个询问包含两只奇诺比奥 $a$ 和 $b$。对于每个询问，你必须计算出从奇诺比奥 $a$ 的房子到奇诺比奥 $b$ 的房子所需的最短时间。

输入格式

输入的第一行包含一个整数 $N$（$2 \le N \le 10^5$），表示奇诺比奥的数量。

接下来的 $N$ 行表示每只奇诺比奥建造的管道。其中第 $i$ 行包含两个空格分隔的整数 $j$（$1 \le j \le N, j \neq i$）和 $t_i$（$1 \le t_i \le 10^9$），表示奇诺比奥 $i$ 的管道连接了他们自己的房子和奇诺比奥 $j$ 的房子，且双向通行需要花费 $t_i$ 的时间。

下一行包含一个整数 $L$（$0 \le L \le 7$），表示奇诺比奥队长建造的额外管道数量。

接下来的 $L$ 行，每行包含三个空格分隔的整数 $x, y, t$（$1 \le x, y \le N, x \neq y, 1 \le t \le 10^9$），表示奇诺比奥队长在奇诺比奥 $x$ 的房子和奇诺比奥 $y$ 的房子之间建造了一条管道，双向通行需要花费 $t$ 的时间。奇诺比奥队长可能会在已经有管道连接的两栋房子之间建造新管道（新管道甚至可能需要更长的通行时间），但他不会在相同的两栋房子之间建造多条管道。

下一行包含一个整数 $Q$（$1 \le Q \le 10^5$），表示询问的数量。

最后 $Q$ 行表示奇诺比奥队长的每个询问。每行包含两个空格分隔的整数 $a$ 和 $b$（$1 \le a, b \le N, a \neq b$），表示每个询问中的两只奇诺比奥。

输出格式

输出 $Q$ 行，表示询问的答案：对于每个询问，输出从一栋房子到另一栋房子所需的最短时间，如果两栋房子之间没有路径，则输出 $-1$。

样例

输入样例 1

5
3 3
4 2
4 1
5 4
2 7
1
5 3 4
3
1 3
2 5
1 5

输出样例 1

3
6
7

输入样例 2

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

输出样例 2

1
5
6

输入样例 3

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

输出样例 3

1
-1