내 이름은 피클! 나는 최고로 전능한 지배자. 하늘처럼 강한 힘으로 명령하는 자일지니! 오너라, 오너라. 화염의 군세여. 내 부름에 응하여 그 힘을 보여라! 익스플로전!

피클은 첫 번째 평행우주의 베르제르그 왕국, 액셀 마을에 살고 있는 정말 유명한 마법사이다.

모두가 알다시피, 베르제르그 왕국은 1부터 $N$까지 번호가 매겨져 있는 $N$개의 마을과 서로 다른 두 마을을 연결하는 $M$개의 도로로 이루어져 있다. 연결하는 마을이 같은 서로 다른 두 도로는 존재하지 않으며, 피클은 도로 하나를 이용할 때마다 $a$원을 지불해야 한다.

또한, 이 세계는 $O$개의 평행우주와 $P$개의 웜홀로 이루어져 있다. 각 우주는 1부터 $O$까지 번호가 매겨져 있고, 각 평행우주에는 정확히 하나의 베르제르그 왕국이 있으며, 모든 우주의 베르제르그 왕국의 구조는 동일하다. 평행우주들은 번호순으로 인접해 있다. 구체적으로, $i$번 평행우주는 $i$가 $1$이 아닌 경우 $i-1$번 평행우주와 인접하고, $i$가 $O$가 아닌 경우 $i+1$번 평행우주와 인접하다. 웜홀들은 인접한 평행우주의 같은 번호의 도시를 연결하며, 이용하려면 $b$원을 지불해야 한다. 예를 들어, 위 그림에는 1번 평행우주의 2번 도시와 2번 평행우주의 2번 도시를 연결하는 웜홀, 2번 평행우주의 4번 도시와 3번 평행우주의 4번 도시를 연결하는 웜홀 등이 있다.

어느 날, 피클은 $O$번째 평행우주의 왕도에서 마법사들의 신문을 판다는 소식을 듣고 그 신문을 사러 가기로 했다. 피클은 슈와슈와를 밀수해야 하기 때문에 신문을 사러 갈 때 돈을 최소한으로 사용해야 하지만, 물가를 잘 몰라 $a$와 $b$의 값을 정확히 알지 못했다. 그래서 피클은 당신에게 $Q$개의 가능한 $a$와 $b$ 값에 대해 필요한 비용을 알려달라고 부탁했다. 피클을 위해 최소 비용을 구해주자.

Input

첫 번째 줄에 베르제르그 왕국의 마을의 수 $N$, 평행우주의 수 $O$, 액셀 마을의 번호 $S$, 그리고 왕도의 번호 $E$가 공백으로 구분되어 주어진다.

두 번째 줄에 도로의 수 $M$이 주어진다.

세 번째 줄부터 $M$개의 줄 중 $i$번째 줄에 도로가 잇는 두 도시의 번호 $s_i, e_i$가 공백으로 구분되어 주어진다.

그다음 줄에 웜홀의 수 $P$이 주어진다.

그다음 $P$개의 줄 중 $i$번째 줄에 웜홀의 정보 $w_i, x_i$가 공백으로 구분되어 주어지며, 이는 $w_i$번째 우주와 $w_i+1$번째 우주의 $x_i$번 도시가 연결되어 있음을 의미한다. 같은 웜홀은 두 번 이상 주어지지 않는다.

그다음 줄에 쿼리의 수 $Q$가 주어진다.

그다음 $Q$개의 줄 중 $i$번째 줄에 두 정수 $a_i, b_i$가 주어진다. 이는 도로 이용 비용이 $a_i$, 웜홀 이용 비용이 $b_i$임을 나타낸다.

$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

쿼리가 주어질 때마다 피클이 신문을 사러 가는 데에 드는 최소 비용을 줄 바꿈으로 구분하여 출력한다. 만약 신문을 살 수 없다면 대신 -1을 출력한다.

Scoring

1. $O = 1$ (30점)

2. $Q = 1$ (15점)

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

4. 추가 제약 조건 없음. (25점)

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