Description

有一个\(n \times m\)的迷宫，里面有一些格子上有障碍物。
你每次可选择上下左右中的一个方向走一步，但不能走出迷宫或走到有障碍物的格子上。
现在有若干组询问，每次询问从一个点走到另一个点至少需要几步。

Format

Input

每个测试点仅包含一组输入数据。
第一行四个整数\(n,m,k,q(1<=n,m<=200000,n \times m<=200000,0<=k<=42,1<=q<=100000)\)，表示迷宫长宽、障碍物数量和询问数量。
接下来\(k\)行每行两个整数\(x,y(1<=x<=n,1<=y<=m)\)，表示一个障碍物的位置。
接下来\(q\)行，每行四个整数\(x_1,y_1,x_2,y_2(1<=x_1,x_2<=n,1<=y_1,y_2<=m)\)，表示询问从\((x_1,y_1)\)走到\((x_2,y_2)\)需要几步。
障碍物位置两两不重合，但询问的起终点可能在障碍物上，这种情况显然不可到达。

Output

按照输入顺序，对于每个询问输出对应的最少步数，如无法到达则输出\(-1\)。

Sample 1

Input

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

Output

6
0
-1
4
-1
5
-1

Sample 2

Input

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

Output

-1

Limitation

5s, 1GB for each test case.

Source

Vijos Original