会場の場所が決まった後、小 T と小 S は祝典会場の設営を始めました。彼らはメイン会場へと続く道に、THUPC の 10 年間の素晴らしい場面を展示するための広い展示エリアを設置しました。

小 T は展示エリアを巨大な格子状に区切り、外周と内部の一部を展示壁にしました。皆が動線に沿って見学しやすいように、彼はすべての展示壁を 4 連結の構造になるよう工夫して設計しました。

見学をより楽しいものにするため、小 S はここで宝探しイベントを開催することにしました。

小 T は展示エリアを $n \times n$ の 2 次元格子として計画しました。格子の最も外側は一連の展示壁で囲まれています。つまり、横座標または縦座標が $0$ または $n+1$ であるすべての格子は展示壁です。さらに、展示エリアの内部には $m$ 個の展示壁があり、そのうち $i$ 番目 ($1 \le i \le m$) の座標は $(x_i, y_i)$ です。すべての展示壁の格子は互いに 4 連結であることが保証されています。

実地でのテストを経て、小 T は格子間を移動する際の所要時間の法則をまとめました。具体的には、格子間には以下の 2 種類の移動方法があります：

• 上下左右方向に 1 マス移動する。すなわち、$(x, y)$ から $(x-1, y), (x+1, y), (x, y-1), (x, y+1)$ のいずれかの隣接する格子へ移動する場合、2 単位時間を消費します。
• 対角線方向に 1 マス移動する。すなわち、$(x, y)$ から $(x-1, y-1), (x-1, y+1), (x+1, y-1), (x+1, y+1)$ のいずれかの対角線上の格子へ移動する場合、3 単位時間を消費します。

当然ながら、移動先の位置が展示壁であってはなりません。注意：対角線方向に移動する際、2 つの対角にある展示壁の格子の隙間を直接通り抜けることができます。 例えば、たとえ $(x, y+1)$ と $(x+1, y)$ の両方が展示壁であったとしても、依然として 3 単位時間を消費して $(x, y)$ から対角線方向に $(x+1, y+1)$ へ直接移動することが可能です。

小 S は展示エリアに合計 $q$ 個の宝物を配置しました。$i$ 番目 ($1 \le i \le q$) の宝物について、彼女はその位置 $(tx_i, ty_i)$ を公表し、その時のあなたの位置は $(sx_i, sy_i)$ です。各宝物を最速で手に入れるために、あなたの現在地から宝物の位置までの最短所要時間を計算してください。

入力

入力の 1 行目には 3 つの正の整数 $n, m, q$ ($1 \le n \le 10^5, 1 \le m, q \le 3 \times 10^5$) が含まれます。

続く $m$ 行のうち、$i$ 行目 ($1 \le i \le m$) には 2 つの正の整数 $x_i, y_i$ ($1 \le x_i, y_i \le n$) が含まれ、これは $i$ 番目の展示壁の座標を表します。すべての $(x_i, y_i)$ は互いに異なることが保証されます。

続く $q$ 行のうち、$i$ 行目 ($1 \le i \le q$) には 4 つの正の整数 $sx_i, sy_i, tx_i, ty_i$ ($1 \le sx_i, sy_i, tx_i, ty_i \le n$) が含まれ、$i$ 番目の宝物が公表された時のあなたの位置と宝物の位置を表します。$(sx_i, sy_i), (tx_i, ty_i)$ はどちらも展示壁ではないことが保証されます。

出力

$q$ 行出力してください。各行に 1 つの整数を出力し、答えを表します。特に、宝物の位置に移動できない場合は $-1$ を出力してください。

入出力例

入力 1

4 4 5
2 1
2 2
3 2
3 3
1 1 1 2
1 1 3 1
4 1 1 4
4 4 1 1
2 3 3 1

出力 1

2
16
11
10
11

注記

2 番目の宝物については、以下の経路で移動できます：$(1, 1) \to (1, 2) \to (2, 3) \to (3, 4) \to (4, 3) \to (4, 2) \to (3, 1)$。総所要時間は $2 + 3 + 3 + 3 + 2 + 3 = 16$ です。