一位游客正在完成挑战。有 $n$ 个城市，编号从 $1$ 到 $n$，城市之间有 $m$ 条双向道路。第 $i$ 条道路连接城市 $u_i$ 和 $v_i$，其难度为 $w_i$，是一个非负整数。

城市 $f$ 和 $t$ 之间的一条路径是一个二元组 $(C, R)$，其中： $C = (c_0, \dots, c_k)$ 是一个城市序列，满足 $c_0 = f$ 且 $c_k = t$。 $R = (r_1, \dots, r_k)$ 是一个道路序列，对于所有 $1 \le i \le k$，道路 $r_i$ 连接城市 $c_{i-1}$ 和 $c_i$。

注意，路径可以多次经过同一个城市，也可以多次经过同一条道路。

如果 $r$ 是一条道路，记 $w(r)$ 为其难度。对于路径 $(C, R)$，定义其难度为 $\max\{w(r) \mid r \in R\}$，定义其哈希值为 $w(r_1) \oplus \dots \oplus w(r_k)$。这里 $x \oplus y$ 表示 $x$ 和 $y$ 的异或（exclusive or）运算。

最后，一个挑战是一个三元组 $(f, t, h)$，表示游客必须从城市 $f$ 出发到达城市 $t$，且所选路径的哈希值必须等于 $h$。

当然，游客希望每个挑战所花费的努力尽可能小。给定 $q$ 个挑战，对于每个挑战，请找出满足约束条件的路径的最小难度，如果无法完成挑战，则报告无解。

输入格式

第一行包含两个整数 $n$ 和 $m$，用空格分隔（$1 \le n, m \le 200\,000$；$n \ge 2$）。

接下来的 $m$ 行，第 $i$ 行包含三个整数 $u_i, v_i, w_i$（$1 \le u_i, v_i \le n$；$0 \le w_i < 2^{30}$），表示第 $i$ 条道路。连接同一对城市的道路可能不止一条，也可能存在连接城市与其自身的道路。城市之间不一定连通，即可能存在某些城市对之间没有路径。

下一行包含一个整数 $q$，表示挑战的数量（$1 \le q \le 200\,000$）。

接下来的 $q$ 行，第 $j$ 行包含三个整数 $f_j, t_j, h_j$（$1 \le f_j, t_j \le n$；$0 \le h_j < 2^{30}$；$f_j \neq t_j$），表示第 $j$ 个挑战。

输出格式

输出 $q$ 个整数，第 $i$ 个整数表示完成第 $i$ 个挑战的路径的最小难度，如果不存在，则输出 $-1$。

样例

输入 1

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

输出 1

-1
2
4