仙人掌图（cactus graph）是一个连通的无向图，没有自环和重边，且每条边最多属于一个简单环。

给定一个包含 $N$ 个顶点（编号为 $1$ 到 $N$）和 $M$ 条边的仙人掌图 $G$。第 $i$ 条边连接顶点 $a_i$ 和 $b_i$，其权值为 $c_i$。

定义一条简单路径的权值为该路径上所有边权值的按位异或和。

回答 $Q$ 个询问，每个询问格式为 “$x_i$ $y_i$ $k_i$”：考虑连接顶点 $x_i$ 和 $y_i$ 的所有简单路径的权值，去除重复值，将这些值按升序排序，并取出第 $k_i$ 个元素。如果这些值的数量少于 $k_i$，则输出 $-1$。

输入格式

第一行包含两个整数 $N$ 和 $M$：图的顶点数和边数（$2 \le N \le 10^5$，$N - 1 \le M \le 2 \cdot 10^5$）。

接下来的 $M$ 行，每行描述一条边，包含三个整数 $a_i$、$b_i$ 和 $c_i$（$1 \le a_i, b_i \le N$，$a_i \neq b_i$，$0 \le c_i < 2^{30}$）。

接下来一行包含一个整数 $Q$：询问次数（$1 \le q \le 2 \cdot 10^5$）。

接下来的 $Q$ 行，每行描述一个询问，包含三个整数 $x_i$、$y_i$ 和 $k_i$（$1 \le x_i, y_i \le N$，$x_i \neq y_i$，$1 \le k_i \le 2^{30}$）。

保证输入的图是一个仙人掌图。

输出格式

对于每个询问，在单独的一行中输出一个整数作为该询问的答案。

样例

样例输入 1

4 4
1 2 2
1 3 8
2 3 0
1 4 6
4
2 1 1
1 2 2
4 1 1
4 3 2020

样例输出 1

2
8
6
-1