给定一个包含 $n$ 个顶点和 $m$ 条边的无向图。顶点编号为 $1, 2, \dots, n$。第 $i$ 条边连接顶点 $u_i$ 和 $v_i$，长度为 $w_i$。这里 $u_i$ 的二进制表示始终是 $v_i$ 二进制表示的前缀。两种二进制表示均不包含前导零。例如，$u_i = 2_{10} = 10_2$，$v_i = 5_{10} = 101_2$。

你需要处理 $q$ 次询问。在第 $i$ 次询问中，给定两个整数 $s_i$ 和 $t_i$。请编写程序计算从顶点 $s_i$ 到顶点 $t_i$ 的最短路径长度，如果它们之间没有路径，则输出 -1。

输入格式

输入仅包含一组测试数据。

第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 100\,000$, $1 \le m \le 200\,000$)，分别表示顶点数和边数。

接下来的 $m$ 行中，第 $i$ 行 ($1 \le i \le m$) 包含三个整数 $u_i, v_i$ 和 $w_i$ ($1 \le u_i < v_i \le n$, $1 \le w_i \le 10^9$)，描述第 $i$ 条边。保证 $u_i$ 的二进制表示是 $v_i$ 二进制表示的前缀。

下一行包含一个整数 $q$ ($1 \le q \le 200\,000$)，表示询问次数。

接下来的 $q$ 行中，第 $i$ 行 ($1 \le i \le q$) 包含两个整数 $s_i$ 和 $t_i$ ($1 \le s_i, t_i \le n, s_i \neq t_i$)，描述第 $i$ 次询问。

输出格式

对于每次询问，输出一行，包含一个整数，表示最短路径的长度。如果不存在路径，则输出 -1。

样例

样例输入 1

5 6
1 2 4
1 3 2
1 4 5
1 5 8
2 4 3
2 5 2
4
2 3
1 4
1 5
4 5

样例输出 1

6
5
6
5

样例输入 2

3 1
1 2 100
3
1 2
1 3
2 3

样例输出 2

100
-1
-1