在一个国家里有 $n$ 座城市。这些城市由 $m$ 条公交线路连接，其中第 $i$ 条线路从城市 $a_i$ 出发，到达城市 $b_i$，耗时 $t_i$ 分钟。

Ema 喜欢旅行，但她不喜欢在公交车之间换乘。在她的旅途中，她希望最多使用 $k$ 条不同的公交线路。

请帮助她回答 $q$ 个询问，每个询问的形式为：“从城市 $c_j$ 到城市 $d_j$ 的最短旅行时间是多少（最多使用 $k$ 条不同的公交线路）？”

输入格式

第一行包含两个正整数 $n$ 和 $m$ ($2 \le n \le 70, 1 \le m \le 10^6$)，分别表示城市数量和公交线路数量。

接下来的 $m$ 行，第 $i$ 行包含三个正整数 $a_i, b_i$ 和 $t_i$ ($1 \le a_i, b_i \le n, 1 \le t_i \le 10^6$)，表示第 $i$ 条公交线路的起点城市、终点城市和旅行时间。

下一行包含两个正整数 $k$ 和 $q$ ($1 \le k \le 10^9, 1 \le q \le n^2$)，表示最多使用的线路数量和询问次数。

接下来的 $q$ 行，第 $j$ 行包含两个正整数 $c_j$ 和 $d_j$ ($1 \le c_j, d_j \le n$)，表示第 $j$ 个询问的起点城市和终点城市。

输出格式

输出 $q$ 行。第 $j$ 行输出第 $j$ 个询问的最短旅行时间，如果不存在满足要求的行程，则输出 -1。

子任务

样例

输入 1

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

输出 1

10
-1
0

输入 2

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

输出 2

6
4
0

输入 3

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

输出 3

3
4
0

说明

样例说明：每个样例的第一个询问的答案已在图中标出。