由於題目太有挑戰性，有啲參賽者決定逃離呢場比賽。不過，為咗防止呢種情況發生，邪惡嘅出題者喺體育場出口整咗個迷宮。迷宮由一個 $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

說明

下圖展示咗第一組樣例嘅迷宮，同第一個查詢嘅情況。

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