由於題目太有挑戰性，有些參賽者決定逃離這場比賽。然而，為了防止這種情況發生，邪惡的出題者在體育館出口處建造了一座迷宮。迷宮由一個 $n \times m$ 的方格網構成，其中有入口、出口，以及 $k$ 個黑洞。不小心踏進任何黑洞的參賽者都會掉進去，再也無法逃離比賽。

更糟的是，出題者還可能調整入口和出口的座標。可憐的你是一名參賽者，從入口出發，希望不踩到任何黑洞而抵達出口，每一步只能移動到四個相鄰格子之一。你想知道，出題者每次改變入口和出口的座標後，從入口到出口最少需要走幾步？

輸入格式

輸入第一行包含四個整數 $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$ 行描述黑洞。每行包含兩個整數 $x,y$（$1 \le x \le n$，$1 \le y \le m$），表示一個黑洞的座標。任意兩個黑洞都不在同一位置。

最後 $q$ 行描述詢問。每行包含四個整數 $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

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

說明

第一組範例資料的迷宮，以及其第一個詢問的示意圖如下。

圖 1：範例測試資料的示意圖。（a）迷宮；（b）第一個詢問的一條可能最短路徑。圖例：入口、出口、黑洞、一步。