Janggi

Interview

Time limit1sMemory limit512 MB

Summary

On a 10x9 janggi board, find the minimum number of elephant moves to reach the king, avoiding the board edges.

Level: Medium4 of 10
Topics: BFS, Graph, Simulation, Implementation
Solved: No attempts yet

Problem

Hogeun, on vacation for the first time in a while, suddenly felt like playing the janggi set in his club room. He had not played in a long time, and he found it very hard to use the elephant properly even though he used to be good at it. Help Hogeun figure out how to move the elephant.

The figure above shows a 10×9 janggi board, with the elephant at (5, 4) and the king at (1, 4). The rectangle with corners (0, 3) and (2, 5), and the rectangle with corners (7, 3) and (9, 5), are the palaces where the king may be placed. The elephant can move in 8 ways as shown above: it moves one cell up, down, left, or right, then two cells diagonally in the same direction.

If another piece lies on the path the elephant moves along, as in the figure above, the elephant cannot move that way. The elephant also cannot leave the board.

Given the starting positions of the elephant and the king on a 10×9 janggi board, find the minimum number of moves for the elephant to reach the king.

Input

The first line gives integers R1, C1, the position of the elephant.

The second line gives integers R2, C2, the position of the king. On the board, Ri (0 ≤ Ri ≤ 9) is the row and Ci (0 ≤ Ci ≤ 8) is the column.

The king is always placed in a palace, and the elephant and the king do not overlap.

Output

Print the minimum number of moves for the elephant to reach the king. If it cannot reach the king, print -1.

Examples3

Example 1
Input
```
4 2
2 5
```
Expected output
```
1
```
Example 2
Input
```
0 1
8 4
```
Expected output
```
3
```
Example 3
Input
```
0 2
1 4
```
Expected output
```
5
```