我的名字是皮克！我是最伟大的全能统治者。我是那个用如天空般强大的力量下达命令的人！来吧，来吧。火焰的军团啊。响应我的召唤，展现你们的力量吧！爆裂魔法（Explosion）！

皮克是生活在第一个平行宇宙中贝尔格雷格（Berzerg）王国阿克塞尔（Axel）镇的一位非常有名的魔法师。

众所周知，贝尔格雷格王国由 $N$ 个城镇组成，编号从 1 到 $N$，并有 $M$ 条连接两个不同城镇的道路。不存在连接相同城镇的重复道路，皮克每使用一条道路需要支付 $a$ 元。

此外，这个世界由 $O$ 个平行宇宙和 $P$ 个虫洞组成。每个宇宙的编号从 1 到 $O$，每个平行宇宙中都有一个完全相同的贝尔格雷格王国，且所有宇宙中王国的结构完全一致。平行宇宙按编号顺序相邻。具体来说，如果 $i \neq 1$，则第 $i$ 号平行宇宙与第 $i-1$ 号平行宇宙相邻；如果 $i \neq O$，则第 $i$ 号平行宇宙与第 $i+1$ 号平行宇宙相邻。虫洞连接相邻平行宇宙中编号相同的城镇，使用虫洞需要支付 $b$ 元。例如，上图中展示了连接第 1 号平行宇宙的 2 号城镇与第 2 号平行宇宙的 2 号城镇的虫洞，以及连接第 2 号平行宇宙的 4 号城镇与第 3 号平行宇宙的 4 号城镇的虫洞等。

有一天，皮克听说第 $O$ 号平行宇宙的王都有卖魔法师报纸，于是决定去买报纸。由于皮克需要走私“舒瓦舒瓦”（Shwa-Shwa），他必须在去买报纸的过程中尽可能少花钱，但他不了解物价，不知道 $a$ 和 $b$ 的确切数值。因此，皮克请求你计算 $Q$ 组可能的 $a$ 和 $b$ 值下所需的最小费用。请帮皮克求出最小费用。

输入格式

第一行包含四个空格分隔的整数，分别是贝尔格雷格王国的城镇数量 $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$ 行中，每行包含两个整数 $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)$

输出格式

对于每个查询，输出皮克前往王都购买报纸所需的最小费用，每个结果占一行。如果无法买到报纸，则输出 -1。

子任务

1. $O = 1$ (30分)

2. $Q = 1$ (15分)

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

4. 无额外限制。(25分)

样例

输入 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

输出 1

9
35
59

输入 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

输出 2

-1
-1

输入 3

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

输出 3

6
36

说明

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