問題があまりに難しいため、コンテストから逃げ出そうとする参加者がいます。しかし、それを防ぐため、邪悪な出題者たちは競技場の出口に迷宮を作りました。迷宮は $n \times m$ のマス目からなり、入口と出口、および $k$ 個のブラックホールがあります。誤ってブラックホールのあるマスに踏み込んだ参加者は、その中に落ちてしまい、二度とコンテストから逃げ出せなくなります。

さらに悪いことに、出題者たちは入口と出口の座標も変更することがあります。あなたは気の毒な参加者で、入口から出発し、どのブラックホールにも踏み込まずに出口にたどり着きたいと思っています。1 歩で移動できるのは、上下左右に隣接する 4 マスのいずれかだけです。出題者たちが入口と出口の座標を変更するたびに、入口から出発して出口にたどり着くために必要な歩数の最小値を求めてください。

入力

入力の最初の行には、4 つの整数 $n,m,k,q$（$1 \le n,m \le 200\,000$、$nm \le 200\,000$、$0 \le k \le 42$、$1 \le q \le 100\,000$）が与えられます。これらは順に、迷宮の行数、列数、ブラックホールの個数、クエリ数を表します。

続く $k$ 行には、ブラックホールの情報が与えられます。各行には、ブラックホールの座標を表す 2 つの整数 $x,y$（$1 \le x \le n$、$1 \le y \le m$）が与えられます。同じ位置に 2 つのブラックホールがあることはありません。

最後の $q$ 行には、クエリの情報が与えられます。各行には、4 つの整数 $x_s,y_s,x_t,y_t$（$1 \le x_s,x_t \le n$、$1 \le y_s,y_t \le m$）が与えられます。$(x_s,y_s)$ が入口の座標、$(x_t,y_t)$ が出口の座標です。

出力

各クエリについて、入口から出発して出口にたどり着くために必要な歩数の最小値を、1 行に 1 つ出力してください。出口にたどり着けない場合は、代わりに $-1$ を出力してください。入口または出口がブラックホールと同じ位置にある場合も、到達不可能とみなしてください。

入出力例

入力 1

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

出力 1

6
0
-1
4
-1
5
-1

入力 2

2 3 2 1
1 2
2 1
1 1 2 3

出力 2

-1

注記

最初の入力例の迷宮と、最初のクエリを表す図を以下に示します。

（a）迷宮。（b）最初のクエリに対する最短経路の一例。凡例：入口、出口、ブラックホール、1 歩。

図 1：入力例を表す図。