The penguins are singing! But as usual, Mumble's going on with his own tap-dancing routine, ignoring everyone elses' weird stares. Today, he's set up a nice grid on the snowy ground and decided to play a simple game of Waddlehops, but with a few modifications.
The Game of Waddlehops
In Waddlehops, each grid cell in the Waddlegrid is known as a Waddlespot. The target of the game is to get from your starting Waddlespot to the target Waddlespot, also known as the Waddlegoal. You can travel from one Waddlespot to another by Hopping horizontally or vertically, but not diagonally. However, there are certain Waddlespots which, because they are set on very very soft snow, will simply cause you to trip and fall if you attempt to step on them. Making sure to avoid these soft Waddlespots, Mumble must get to the Waddlegoal in as few Hops as possible.
Simple enough? Not quite. You see, Mumble is a very very talented tap-dancer, and this boring Hopping poses no challenge to him. He has modified the game a little, but as you will see, this makes it far more difficult. Instead of just getting to the Waddlegoal, Mumble decides that he must end up facing in the exact same direction as the Waddlegoal. Also, instead of Hopping from one Waddlespot to the next, Mumble allows himself only three types of moves.
He can Splin to the next Waddlespot, such that he will end up in the neighbouring Waddlespot, but facing 90 degrees to his right. This is quite a simple maneuver, and takes about as much effort as one Hop. He can also Splun to an adjacent Waddlespot, ending up in that Waddlespot but facing 90 degrees to his left. Since he is right-footed, this is much harder for him, and takes twice the effort. He can also Flop to an adjacent square. When he Flops sideways, he remains facing the same direction as before, but if he Flops forwards or backwards, he will end up facing the opposite direction. Flops are, as you can tell, very complicated, so each Flop takes four times the effort of a single Splin.
Why go to all this trouble? Well, as we've already said, Mumble is a very very talented tap-dancer, but that doesn't mean he has no room for improvement. He'd rather train than waste his time rolling about in the snow. Anyway, Mumble also has a very good sense of direction (how else did he get all the way across the ocean?) and feels that the direction he faces when he's on a Waddlespot matters a lot. All this Splinning, Splunning and Flopping confuses the Great Guin out of him though, and he wants to know if his Waddlehop sequence is the best there is.
Given the size of the Waddlegrid, the positions of the soft Waddlespots, Mumble's initial position and orientation, and the position and orientation of the Waddlegoal, determine the smallest amount of effort (in terms of Hops) needed for Mumble to get to the Waddlegoal.
Input
The first line of the input contains n, m and s, the number of rows and columns in the Waddlegrid and the number of soft Waddlespots.
The following s lines contain two integers each, ri and ci, the row and column coordinates of each soft Waddlespot.
The next line contains ar, ac and ao, representing Mumble's initial row and column coordinates and orientation.
The last line contains br, bc and bo, similarly representing the row, column and orientation of the Waddlegoal.
Output
Output a single integer representing the smallest amount of effort (in Hops) needed to get to the Waddlegoal, or -1 if the Waddlegoal cannot be reached at all.
Limits
1 < n, m ≤ 1000, n * m ≥ 2.
0 ≤ s ≤ n * m.
0 ≤ ri, ar, br < n.
0 ≤ ci, ac, bc < m.
Sample Input 1
4 4 4
1 1
1 2
2 1
2 2
0 0 0
3 3 2
Sample Output 1
6
Sample Input 2
1 2 0
0 0 0
0 1 2
Sample Output 2
6
Sample Input 3
1 3 1
0 1
0 0 0
0 2 0
Sample Output 3
-1