Time Limit: 1000 MS Memory Limit: 524288 K


Description

下路一直叫我去,我怎么去啊?对面酒桶一直在我野区。我当时就很想说的,但我也没说。就我说什么你们也没有在听,说什么你们也不给我反馈,莫名其妙的感觉我们这。

我们把野区当做n x m的网格图,里面有很多障碍,7酱在野区中打野,一开始7酱位于位置s,每一回合他有三种操作:前进一格到合法位置,向左转1/4周,向右转1/4周。一开始7酱可以选择面向任意一个方向。

现在有q个询问,每次给出一个目的地,要求7酱最少转向次数。

Input

第一行四个整数 n,m,k,q,表示网格的行数和列数,障碍的个数,以及询问的个数。接下来 k 行障碍,每行两个正整数 x, y,表示第 x行,y列有一个障碍,保证障碍的位置两两不同。接下来一行两个正整数 x,y,表示起点 s 在第 x 行,y 列,保证起点处没有障碍。接下来 q行描述询问,每行两个正整数x,y,表示这次询问的终点在第 x 行,y 列,保证终点处没有障碍。()

Output

输出:输出共 q 行,每行一个正整数,其中第 i行的数表示第 i个询问的答案。如果第 i个询问中无法到达终点输出-1

Sample Input

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

Sample Output

-1
1
0
1
1
0
3
2
0