In a country there are cities. The cities are connected by bus routes, where the route starts in city , ends in city and takes minutes.

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

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

#### Input Specification

The first line contains two positive integers and , the number of cities and the number of bus routes.

The of the next lines contains positive integers , , and , the terminal cities and the travel time of the bus route.

The next line contains two positive integers and , the maximum number of used routes and the number of queries.

The of the next lines contains positive integers and , the cities from the query.

#### Output Specification

Print lines. In the line, print the shortest travel time from the query, or `-1`

if there is no trip
that satisfies the requirements.

#### Constraints

Subtask | Points | Constraints |
---|---|---|

1 | 15 | |

2 | 15 | |

3 | 25 | |

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
```

## Comments