Background

Fujiwara no Mokou, who has gained the power of “immortality”, also obtained the ability to control flames, and became the incarnation of a firebird.

Are a firebird and a phoenix the same kind of creature?

Problem Description

Mokou can control a firebird. The firebird can be seen as a piece $A$ placed on an infinitely large chessboard, with $A$ located at $(x_1,y_1)$. $A$ moves by the following rules:

• On odd-numbered moves, $A$ can only move one square to the upper-right or lower-left, as shown by the red arrows in the figure.
• On even-numbered moves, $A$ can only move one square to the lower-right or upper-left, as shown by the blue arrows in the figure.

Because the board is infinite, $x$ and $y$ may be negative.

In each step, $A$ cannot stay in place. Now we need to move $A$ to position $B$ with coordinates $(x_2,y_2)$. What is the minimum number of steps? In particular, if no such plan exists, output $-1$.

The figure below shows the case $A=(2,7)$ and $B=(5,2)$. One optimal plan is marked in the figure and requires $9$ steps. Red segments represent odd-numbered moves, and blue segments represent even-numbered moves.

Input Format

The input consists of one line with four integers $x_1,y_1,x_2,y_2$, describing the coordinates of $A$ and $B$.

Output Format

Output one line with one integer. If there exists a move sequence from $A$ to $B$, output the minimum number of steps; otherwise output $-1$.

2 7 5 2

9

2 2 3 2

-1

0 0 1000000000 1000000000

2000000000

Hint

Constraints and Notes

For all testdata, it is guaranteed that $0\le x_1,y_1,x_2,y_2\le 10^9$.

Translated by ChatGPT 5