Knight's Marathon

After an exhausting battle, the invading army is finally defeated. The king sends his only surviving knight to the kingdom’s capital to tell the people of your victory. This might be a very (very!) long journey.

\includegraphics[width=0.25\textwidth ]{moves}
Figure 1: The possible moves for a knight.

The knight moves as on a chessboard: in each move, he travels two squares in one of the four compass directions, and one more square sideways. During his journey, he must remain inside the kingdom to avoid starting any new wars. The kingdom is a $N_ X \times N_ Y$ rectangular grid, which is possibly much (much!) larger than the $8 \times 8$ board on which the battle was fought. The rows and columns in this kingdom are numbered from $0$. The knight starts at square $K_ X, K_ Y$, and must travel to the capital at square $C_ X, C_ Y$. Output the smallest number of moves in which the knight can reach the capital.


The input consists of three lines, each containing two integers:

  • On the first line: $N_ X, N_ Y$, the size of the kingdom, with $8 \leq N_ X, N_ Y \leq 10^9$.

  • On the second line: $K_ X, K_ Y$, the knight’s starting position, with $0 \leq K_ X < N_ X$ and $0 \leq K_ Y < N_ Y$.

  • On the third line: $C_ X, C_ Y$, the position of the capital, with $0 \leq C_ X < N_ X$ and $0 \leq C_ Y < N_ Y$.


Output a single line containing a single integer, the number of moves the knight will need to get to the capital.

Sample Input 1 Sample Output 1
8 8
0 0
7 7
Sample Input 2 Sample Output 2
1000 7000
253 6789
253 6789
Sample Input 3 Sample Output 3
8 1000000000
3 3
3 999999999