In a country there are $n$ cities. The cities are connected by $m$ bus routes, where the $i^{\text{th}}$ route starts in city $a_i$, ends in city $b_i$ and takes $t_i$ minutes.

Ema loves to travel, but doesn't like transferring between buses. On her trip she wants to use at most $k$ different bus routes.

Help her answer $q$ questions of the form "What is the shortest travel time to get from city $c_j$ to city $d_j$ (using at most $k$ different bus routes)?".

Input Specification

The first line contains two positive integers $n$ and $m$ $(2\le n\le 70,1\le m\le {10}^6)$, the number of cities and the number of bus routes.

The $i^{\text{th}}$ of the next $m$ lines contains positive integers $a_i$, $b_i$, and $t_i$ $(1\le a_i,b_i\le n,1\le t_i\le {10}^6)$, the terminal cities and the travel time of the $i^{\text{th}}$ bus route.

The next line contains two positive integers $k$ and $q$ $(1\le k\le {10}^9,1\le q\le n^2)$, the maximum number of used routes and the number of queries.

The $j^{\text{th}}$ of the next $q$ lines contains positive integers $c_j$ and $d_j$ $(1\le c_j,d_j\le n)$, the cities from the $j^{\text{th}}$ query.

Output Specification

Print $q$ lines. In the $j^{\text{th}}$ line, print the shortest travel time from the $j^{\text{th}}$ query, or -1 if there is no trip that satisfies the requirements.

Constraints

Subtask	Points	Constraints
1	15	$k\le n\le 7$
2	15	$k\le 3$
3	25	$k\le n$
4	15	No additional constraints.

Sample Input 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

Sample Output 1

10
-1
0

Explanation for Sample Output 1

The answer to the first query from each example is marked on the graph.

Sample Input 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

Sample Output 2

6
4
0

Sample Input 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

Sample Output 3

3
4
0