Peter the penguin is lost in an icy cave! Upon closer observation, he notices that he can represent the cave as an 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 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 adverse 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 and another at ), they are counted separately (i.e. he has slid over rock patches).

**Note: The cave is unbounded (i.e. there are no walls).**

#### Input Specification

Line : two space separated integers, and .

Line : two space separated integers, and , Peter's starting position.

Line : an integer, .

Lines : two space separated integers, and , which represent the position of an obstacle. It is guaranteed that Peter's starting position will never be an obstacle.

Line : an integer, , the number of exits.

Lines , two integers, , and , 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 of points, .

#### 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.

I think it's "what is the minimum number of times."

Thanks! It's been fixed.

In how many directions can the penguin move?

It would appear, judging by the sample case, only horizontally and vertically.

Statement has been updated to reflect this.

Follow-up question: Can Peter choose which direction he starts in?

Yes.

Peter will

slide ontoa rock patch and stop.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