Peter the penguin is lost in an icy cave! Upon closer observation, he notices that he can represent the cave as an 
~N \times M~ rectangle in the Cartesian plane. However, the ice is very slippery, and he can only stop and change directions when he slides onto one of 
~O~ rock patches. In addition to this, he fears getting lost, so he will only move parallel to the axes.
Peter, much like any other sane penguin, is averse to sliding onto a rock patch, and as such, wishes to ask you a question: what is the minimum number of times he will do so while escaping the cave?
If there are two adjacent rock patches, (e.g. one at 
~(2, 2)~ and another at 
~(2, 3)~), they are counted separately (i.e. he has slid over 
~2~ rock patches).
Note: The cave is unbounded (i.e. there are no walls).
Input Specification
Line 
~1~: two space separated integers, 
~N~ and 
~M~ 
~(1 \le N, M \le 10^9)~.
Line ~2~: two space separated integers, 
~X~ 
~(1 \le X \le N)~ and 
~Y~ 
~(1 \le Y \le M)~, Peter's starting position.
Line 
~3~: an integer, ~O~ 
~(1 \le O \le 10^5)~.
Lines 
~4 \dots O+3~: two space separated integers, 
~x_i~ 
~(1 \le x_i \le N)~ and 
~y_i~ 
~(1 \le y_i \le M)~, which represent the position of an obstacle. It is guaranteed that Peter's starting position will never be an obstacle.
Line 
~O+4~: an integer, 
~E~ 
~(1 \le E \le 10^5)~, the number of exits.
Lines 
~O+5 \dots O+E+4~, two integers, ~x_i~ ~(1 \le x_i \le N)~, and ~y_i~ ~(1 \le y_i \le M)~, the coordinates of an exit. It is guaranteed that Peter's starting position will never be an exit, and that no exit will contain an obstacle.
Output Specification
The output should consist of one integer, the minimum number of times Peter will slide over a rock patch while escaping the cave. If it is not possible to escape the cave, output -1 instead.
Subtasks
For 
~20\%~ of points, 
~N, M \le 1\,000~.
Sample Input
10 10
1 1
3
4 4
4 1
8 9
2
10 4
2 8
Sample Output
2
Comments
What's wrong with my code? I WA test case 3 of batch 1 and test case 6 of batch 2, but I have no idea why it doesn't work. I've made up a few test cases but it works for all of them. I'm fairly certain there's no issue with how I'm storing the adjacent rocks, so is there a problem with my binary search?
https://dmoj.ca/problem/helloworld#comment-5742
If the penguin is sliding towards two rock patches, one behind the other, will it stop when it gets to the first rock patch, or slide over both? If it stops at the first rock patch will it still count as sliding over two rock patches?
He will stop at the first one, and the patches are counted separately (i.e. 2 patches).
So when the penguin stops at the first rock patch (that is connected to another rock patch), you must say that the penguin slid over 2 rock patches?
No, you only count the number of individual squares which Peter slides on. If he were to stop at the first rock, it would count as 1. However, if he were to slide over both of them, then that would count as 2.
Will the penguin stop if it hits a wall?
What walls are you referring to? The cave is unbounded (not surrounded by walls). He'll just slide off to infinity.
If so, wouldn't it be more appropriate to represent the cave with a rectangle that is infinitely large? What would be the point of
or 
then?
For a more convenient representation of subtasks.
If a penguin slides over an exit, will it stop at the exit or overshoot the exit? (assuming no rocks are nearby)
Yes, he will always stop at the exit