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