Regular checkup

Time limit1.5sMemory limit256 MB

Summary

In a graph split by a river with B bridges, answer Q queries for the shortest travel time from a given house to a given hospital, or -1 if unreachable.

Level: Medium7 of 10
Topics: Graph, Shortest path, Dynamic programming, Matrix
Solved: No attempts yet

Problem

The residents of DD Planet travel to a hospital for a regular checkup.

DD Planet has $N$ houses (numbered $1, 2, \dots, N$ ) and $M$ hospitals (numbered $N+1, N+2, \dots, N+M$ ). A deep river separates the area holding the houses from the area holding the hospitals. Crossing the river is possible only over a bridge. There are $B$ bridges (numbered $N+M+1, N+M+2, \dots, N+M+B$ ), and crossing any bridge takes $0$ seconds.

DD Planet also has $K$ roads that join houses, hospitals, and bridges. A road between two bridges is allowed. Because the deep river runs between the two areas, no road joins a house directly to a hospital.

Answer $Q$ questions.

What is the minimum time for a resident of house $S_i$ to reach hospital $E_i$ ?

Input

The first line contains the number of houses $N$ and the number of hospitals $M$ ( $1 \le N, M \le 10\,000$ ), the number of bridges $B$ ( $1 \le B \le 100$ ), the number of roads $K$ ( $1 \le K \le 2 \times 10^4$ ), and the number of questions $Q$ ( $1 \le Q \le 10^5$ ), separated by spaces.

Each of the next $K$ lines contains three integers $a$ , $b$ , and $K_i$ , separated by spaces. A road joins point $a$ and point $b$ , and travelling along that road takes $K_i$ ( $1 \le K_i \le 10^9$ ) time.

Each of the next $Q$ lines contains $S_i$ and $E_i$ for one question, separated by spaces. ( $1 \le S_i \le N$ , $N+1 \le E_i \le N+M$ )

Output

On line $i$ , print the answer to question $i$ . If house $S_i$ cannot reach hospital $E_i$ , print $-1$ .

Examples4

Example 1

Input

Expected output

5
4

Example 2

Input

Expected output

7
-1
-1

Example 3

Input

Expected output

Example 4
Input
```
1 1 2 3 1
1 3 5
3 4 2
4 2 7
1 2
```
Expected output
```
14
```