Distance in Crosses

Time limit2sMemory limit512 MB

Summary

Squares are tiled by crosses whose centers form a lattice; moving to a different cross costs one coin, and we must find the minimum coins between two given squares.

Level: Hard8 of 10
Topics: Math, Geometry, Shortest path, Implementation
Solved: No attempts yet

Problem

The plane is divided into squares with side $1$ . Choose one square and draw coordinate axes from its center parallel to its sides.

Next, draw a cross made up of the central square and its four neighbors, the squares sharing a side with it. Then pick the square centered at $(2, 1)$ and draw another cross made up of this square and its four neighbors. Tile the whole plane with such crosses: their centers lie at the points with coordinates $(2 i + j, i - 2 j)$ for all integer $i$ and $j$ . The tiling appears in the figure next to the examples.

Emilia stands at the center of some square on the plane. In one step she can move from a square to one of its neighbors. If a step takes her to a different cross of the tiling, she must pay one coin for that step. Steps that keep her in the same cross are free.

Let the distance in crosses between two squares $A$ and $B$ be the minimum number of coins Emilia must pay to get from $A$ to $B$ . You are given the coordinates of two points on the plane: the center of the starting square and the center of the destination square. Find the distance in crosses between them.

Input

The first line contains two integers $x\_1$ and $y\_1$ , the coordinates of the starting square. The second line contains two integers $x\_2$ and $y\_2$ , the coordinates of the destination square. The absolute value of every given coordinate does not exceed $10^{9}$ .

Output

Print one integer: the distance in crosses from the starting square to the destination square.

Examples3

Example 1
Input
```
1 1
2 2
```
Expected output
```
0
```
Example 2
Input
```
3 4
-2 0
```
Expected output
```
4
```
Example 3
Input
```
4 3
0 -2
```
Expected output
```
3
```