My name is Pickle! I am the most omnipotent ruler. I am the one who commands with power as strong as the heavens! Come, come. Army of flames. Respond to my call and show your power! Explosion!

Pickle is a very famous wizard living in Axel, a town in the Bergzerg Kingdom of the first parallel universe.

As everyone knows, the Bergzerg Kingdom consists of $N$ towns numbered from 1 to $N$ and $M$ roads connecting two distinct towns. There are no two different roads that connect the same pair of towns, and Pickle must pay $a$ to use each road.

Furthermore, this world consists of $O$ parallel universes and $P$ wormholes. Each universe is numbered from 1 to $O$, and each parallel universe contains exactly one Bergzerg Kingdom, with all kingdoms having the same structure. The parallel universes are adjacent in numerical order. Specifically, universe $i$ is adjacent to universe $i-1$ if $i \neq 1$, and adjacent to universe $i+1$ if $i \neq O$. Wormholes connect towns with the same number in adjacent parallel universes, and using one costs $b$. For example, the image above shows a wormhole connecting town 2 in universe 1 to town 2 in universe 2, and a wormhole connecting town 4 in universe 2 to town 4 in universe 3, etc.

One day, Pickle heard that the capital of the $O$-th parallel universe sells newspapers for wizards, so he decided to go buy one. Since Pickle has to smuggle "Shwa-Shwa," he wants to minimize the money spent on his trip, but he does not know the exact values of $a$ and $b$ because he is unfamiliar with the cost of living. Therefore, Pickle has asked you to calculate the required cost for $Q$ possible pairs of $a$ and $b$. Let's find the minimum cost for Pickle.

Input

The first line contains the number of towns $N$, the number of parallel universes $O$, the number of the starting town $S$, and the number of the capital town $E$, separated by spaces.

The second line contains the number of roads $M$.

Each of the next $M$ lines contains two integers $s_i, e_i$, the two towns connected by the $i$-th road, separated by spaces.

The next line contains the number of wormholes $P$.

Each of the next $P$ lines contains two integers $w_i, x_i$, meaning there is a wormhole connecting town $x_i$ in universe $w_i$ to town $x_i$ in universe $w_i+1$, separated by spaces. No wormhole is given more than once.

The next line contains the number of queries $Q$.

Each of the next $Q$ lines contains two integers $a_i, b_i$, representing the cost to use a road and the cost to use a wormhole, respectively.

$1 \le N \le 5000$ $1 \le O \le 1000$ $1 \le S, E \le N$ $0 \le M \le 10^4$ $1 \le s_i, e_i \le N \, (1\le i \le M)$ $0 \le P \le 10^4$ $1 \le w_i \le O-1;\ 1 \le x_i \le N \, (1\le i \le P)$ $1 \le Q \le 10^4$ $0 \le a_i, b_i \le 100\, (1\le i \le Q)$

Output

For each query, output the minimum cost for Pickle to reach the capital on a new line. If it is impossible to reach the capital, output -1 instead.

Subtasks

1. $O = 1$ (30 points)

2. $Q = 1$ (15 points)

3. $M = N - 1$, $s_i = i$, $e_i = i+1$ (30 points)

4. No additional constraints. (25 points)

Examples

Input 1

6 3 4 3
7
1 2
1 4
2 3
3 4
3 6
5 6
5 4
4
1 2
1 6
2 4
2 5
3
1 2
3 10
9 7

Output 1

9
35
59

Input 2

8 4 1 8
8
1 2
2 3
2 4
2 5
4 5
6 7
6 8
7 8
5
1 3
2 2
2 6
2 5
3 3
2
1 6
57 15

Output 2

-1
-1

Input 3

5 1 2 3
4
2 1
1 5
1 4
5 3
0
2
2 3
12 16

Output 3

6
36

Note

https://www.youtube.com/watch?v=EOq3bn743_I