Knight's Marathon

Time limit2sMemory limit512 MB

Summary

On a huge rectangular board, find the minimum number of knight moves from one square to another while staying inside the board.

Level: Hard8 of 10
Topics: Math, BFS, Greedy, Geometry
Solved: No attempts yet

Problem

The invading army is beaten at last. The king sends his only surviving knight to the capital to tell the people about the victory. The trip may be a very long one.

The knight moves the way a knight moves on a chessboard. In one move he travels two squares in one of the four compass directions, then one more square at a right angle to that direction. He must stay inside the kingdom for the whole trip so that he does not start a new war. The kingdom is a rectangular grid of size $NX \times NY$ , possibly much larger than the $8 \times 8$ board the battle was fought on. Rows and columns are numbered from 0. The knight starts at square $(KX, KY)$ and must reach the capital at square $(CX, CY)$ . Find the smallest number of moves in which the knight can reach the capital.

The squares a knight can reach in one move

Figure 1: the squares a knight can reach in one move.

Input

The input has three lines, each with two integers.

The first line has the size of the kingdom, $NX$ and $NY$ ( $8 \le NX, NY \le 10^9$ ).
The second line has the starting position of the knight, $KX$ and $KY$ ( $0 \le KX < NX$ , $0 \le KY < NY$ ).
The third line has the position of the capital, $CX$ and $CY$ ( $0 \le CX < NX$ , $0 \le CY < NY$ ).

Output

Print one line with the smallest number of moves the knight needs to reach the capital.

Examples3

Example 1
Input
```
8 8
0 0
7 7
```
Expected output
```
6
```
Example 2
Input
```
1000 7000
253 6789
253 6789
```
Expected output
```
0
```
Example 3
Input
```
8 1000000000
3 3
3 999999999
```
Expected output
```
499999998
```