問題文

この問題の実行時間制限は3500[ms]です。

問題文

正整数 $N$ と$xy$ 平面内の相異なる $N$ 個の点からなる集合 $S$ と、正整数 $M$ と $xy$ 平面内の相異なる $M$ 個の点からなる集合 $T$ が与えられます。

$S$ の要素 $s = (x,y)$ と $T$ の要素 $t = (z,w)$ の距離 $d(s,t)$ を、$\ell^1$ 距離（マンハッタン距離）

$\displaystyle |x-z| + |y-w| $

として定めます。更に $S$ と $T$ の距離 $D(S,T)$ を、$s$ と $t$ をそれぞれ $S$ と $T$ の要素全体をわたらせた時の $d(s,t)$ の最小値

$\displaystyle \min_{(s,t) \in S \times T} d(s,t) $

として定めます。$D(S,T)$ を求めてください。

入力

$S$ の要素を $N$ 以下の各正整数 $n$ で番号付けし $s_n = (x_n,y_n)$ と置き、$T$ の要素を $M$ 以下の各正整数 $m$ で番号付けし $t_m = (z_m,w_m)$ と置きます。

この時、入力は以下の形式で標準入力から $2 + N + M$ 行で与えられます：

• $1$ 行目に $N$ が与えられます。
• $N$ 以下の各正整数 $n$ に対し、$1 + n$ 行目に $x_n, y_n$ が半角空白区切りで与えられます。
• $2 + N$ 行目に $M$ が与えられます。
• $M$ 以下の各正整数 $m$ に対し、$2 + N + m$ 行目に $z_m, w_m$ が半角空白区切りで与えられます。

$N$
$x_1$ $y_1$
$\vdots$
$x_N$ $y_N$
$M$
$z_1$ $w_1$
$\vdots$
$z_M$ $w_M$

制約

入力は以下の制約を満たします：

• $N$ は $1 \leq N \leq 2 \times 10^5$ を満たす整数である。
• $N$ 以下の任意の正整数 $n$ に対し、
• $x_n$ は $0 \leq x_n < 10^3$ を満たす整数である。
• $y_n$ は $0 \leq y_n < 10^3$ を満たす整数である。
• $N$ 以下の任意の正整数 $n_0, n_1$ に対し、$n_0 \neq n_1$ ならば $s_{n_0} \neq s_{n_1}$ である。
• $M$ は $1 \leq M < 2 \times 10^5$ を満たす整数である。
• $M$ 以下の任意の正整数 $m$ に対し、
• $z_m$ は $0 \leq z_m < 10^3$ を満たす整数である。
• $w_m$ は $0 \leq w_m < 10^3$ を満たす整数である。
• $M$ 以下の任意の正整数 $m_0, m_1$ に対し、$m_0 \neq m_1$ ならば $t_{m_0} \neq t_{m_1}$ である。

出力

$D(S,T)$ を $1$ 行に出力してください。

サンプル

1
0 0
1
1 1

2

2
0 1
1 0
2
1 0
1 1

0

3
0 0
1 0
2 0
2
0 1
1 1

1