1174 - うわ！ラーメンマン現る！

問題

HOJ市は、東西方向にまっすぐに伸びる$H$本の道路と、南北方向にまっすぐに伸びる$W$本の道路で碁盤の目のように区切られている。道路と道路の間隔は1である。また、北から$i$本目$(1 \le i \le H)$の道路と西から$j$本目$(1 \le j \le W)$の道路の交差点を$(i, j)$と呼ぶ。

HOJ市にはn店のラーメン屋があり、$i$番目のラーメン屋は、交差点$(SY_i, SX_i)(1 \le i \le n)$のそばである。

ラーメン好きの寅さんが今度HOJ市に引っ越すことになった。引っ越し予定地は$m$件あり、$j$件目の候補地は交差点$(TY_j, TX_j)(1 \le j \le m)$のそばである。

あなたの仕事は寅さんのために、すべての候補地について最寄りのラーメン屋までの最短距離を求めることである！

制約

$1 \le n, m \le 1000$
$1 \le H, W \le 10^5$
$1 \le SY_i, TY_j \le H$ $(1 \le i \le n)$ $(1 \le j \le n)$
$1 \le SX_i, TX_j \le W$ $(1 \le i \le n)$ $(1 \le j \le m)$

ただし、同じ交差点に複数のラーメン屋や複数の候補地が置かれることは無い。ラーメン屋と候補地が同じ交差点に置かれることもない。

また、寅さんは必ず道路に沿って移動する。

入力

1行目に、道路の数$H, W$が与えられる

2行目に、ラーメン屋の数$n$と引っ越し候補地の数$m$が与えられる

続くn行にはラーメン屋の位置が与えられる

続くm行には引っ越し候補地の位置が与えられる

H W
n m
SY1 SX1
...
SYn SXn
TY1 TX1
...
TYm TXm 

出力

$m$行にわたって最短路長を出力せよ

$i$行目には、候補地$i$から最寄りのラーメン屋までの最短路長を求めよ

例えば $m = 2$ のとき、出力は2行になる。改行を忘れないこと。

小課題

1.$(6点)$ $n \le 100$, $m = 1$ かつ $1 \le h \le 1000$, $1 \le w \le 1000$

2.$(9点)$ $1 \le h \le 1000$, $1 \le w \le 1000$

3.$(85点)$ 追加の制約は無い

入出力例

No.1

入力

10 10
1 1
9 9
8 8

出力

2

(8, 8)から(9, 9)に行くには、たとえば(8, 9)に移動してから(9, 9)に移動する。必ず道路に沿って移動することに注意せよ。

No.2

入力

10 10
2 1
8 8
7 6
5 5

出力

3