由于题目难度较大，一些参赛者决定逃离这场比赛。然而，为了防止这种情况发生，邪恶的出题人在体育场的出口处设置了一个迷宫。迷宫由一个 $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：样例测试数据示意图