#546. 「LibreOJ β Round #7」网格图

给定一张 的网格图，行标号为 到 ，列标号为 到 ，网格图上设置了 个障碍。

一个机器人在网格图中行走，初始时它位于位置 ，每一时刻他有三种行动方式：

1. 如果自己面向的方向不是障碍或网格的边缘，向该方向前进一格。
2. 向左（逆时针）转四分之一周。
3. 向右（顺时针）转四分之一周。

初始时机器人可以选择面向任意一个方向。

现在有 个询问，每个询问给定一个终点 ，请你求出他从 到 最少需要的转向次数（即行动 2 和 3 的总次数，但初始时选择方向不算做转向），每次选择的初始方向可以不同。

第一行四个整数 ，表示网格的行数和列数，障碍的个数，以及询问的个数。

接下来 行描述障碍，其中第 行两个正整数 ，表示第 行， 列有一个障碍，保证障碍的位置两两不同。

接下来一行两个正整数 ，表示起点 在第 行， 列，保证起点处没有障碍。

接下来 行描述询问，其中第 行两个正整数 ，表示第 次询问的终点 在第 行，列，保证终点处没有障碍。

输出共 行，每行一个正整数，其中第 的数表示第 个询问的答案。如果第 个询问中从起点 无法到达终点 ，则第 行输出 -1。

样例输入 1

3 4 3 9
1 2
2 1
3 3
3 4
1 1
1 3
1 4
2 2
2 3
2 4
3 1
3 2
3 4

样例输出 1

-1
1
0
1
1
0
3
2
0

样例解释 1

地图如下（. 表示空地，# 表示障碍，S 表示起点，下同）：

.#..
#...
..#S

样例输入 2

3 3 0 9
2 2
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

样例输出 2

1
0
1
0
0
0
1
0
1

样例解释 2

地图如下：

...
.S.
...

样例输入 3

5 7 4 6
1 4
1 6
2 5
5 4
1 1
1 5
2 4
2 7
4 1
4 6
5 7

样例输出 3

-1
1
2
0
1
2

样例解释 3

地图如下：

S..#.#.
....#..
.......
.......
...#...

对于所有数据，，保证起点和终点处没有障碍，障碍的位置两两不同。