Kookmin Land

Kookmin University decided to build an amusement park called Kookmin Land so that students enjoy their vacation. Hyunwoo, who is in charge of the whole project, picked four points on the campus map and planned to use the quadrilateral formed by those points as the site of Kookmin Land. The four points he picked are shown below.

The university cares about how the park looks, so it rejected Hyunwoo's proposal and added a condition for choosing the new site.

"Kookmin Land must be a square whose side length is at least 1. The side length must be an integer, and each side must be parallel to the $x$ axis or the $y$ axis. The point where the two diagonals of the square meet must always be $(0, 0)$."

In other words, a square of side length $L$ has the four vertices $(L/2, L/2)$, $(L/2, -L/2)$, $(-L/2, L/2)$ and $(-L/2, -L/2)$. When $L$ is odd, the vertices do not have integer coordinates.

Hyunwoo now moves the four points he picked first and chooses a new site that meets the condition. One crew is already stationed at each of the four points, so the crews must move in such a way that every vertex of the new square holds exactly one crew. Hyunwoo decides which crew goes to which vertex. Moving one crew costs the Manhattan distance between its old coordinates and its new coordinates, $|x_{old} - x_{new}| + |y_{old} - y_{new}|$, and the total cost is the sum of the moving costs of the four crews.

The left picture changes the plan to a square of side length 8. Moving the crews from the black points (old coordinates) to the red points (new coordinates) costs 7 at the least. If the plan changes to a square of side length 10 as in the right picture, the least cost becomes 3, and no square of any size brings the cost below 3.

Write a program that finds the side length of Kookmin Land with the smallest total moving cost. If several squares share the smallest cost, take the largest one among them.

The input is read from standard input and consists of one test case. It has four lines, and each line holds the coordinates $x$ and $y$ of one of the points Hyunwoo picked first, separated by a space. Both coordinates are integers with $|x| \le 10^9$ and $|y| \le 10^9$. Some of the four points may share the same coordinates.

Print to standard output, on one line, the side length of the square with the smallest total moving cost. If several squares reach that smallest cost, print the side length of the largest one among them.