Score : $300$ points

问题陈述

有一个无限的二维网格，我们有一个叫做超级龙马的棋子位于方格 $(r_1, c_1)$。（龙代表龙，马代表马。） 在一步移动中，棋子可以移动到以下所示的方格之一：

更正式地说，当超级龙马位于方格 $(a, b)$ 时，它可以移动到方格 $(c, d)$，使得至少满足以下条件之一：

• $a + b = c + d$
• $a - b = c - d$
• $|a - c| + |b - d| \le 3$

找出棋子从 $(r_1, c_1)$ 移动到 $(r_2, c_2)$ 所需的最少步数。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

There is an infinite two-dimensional grid, and we have a piece called Super Ryuma at square $(r_1, c_1)$. (Ryu means dragon and Ma means horse.) In one move, the piece can go to one of the squares shown below:

More formally, when Super Ryuma is at square $(a, b)$, it can go to square $(c, d)$ such that at least one of the following holds:

• $a + b = c + d$
• $a - b = c - d$
• $|a - c| + |b - d| \le 3$

Find the minimum number of moves needed for the piece to reach $(r_2, c_2)$ from $(r_1, c_1)$.

Constraints

• All values in input are integers.
• $1 \le r_1, c_1, r_2, c_2 \le 10^9$

Input

Input is given from Standard Input in the following format:

$r_1$ $c_1$

$r_2$ $c_2$

Output

Print the minimum number of moves needed for Super Ryuma to reach $(r_2, c_2)$ from $(r_1, c_1)$.

Sample Input 1

1 1
5 6

Sample Output 1

2

We need two moves - for example, $(1, 1) \rightarrow (5, 5) \rightarrow (5, 6)$.

Sample Input 2

1 1
1 200001

Sample Output 2

2

We need two moves - for example, $(1, 1) \rightarrow (100001, 100001) \rightarrow (1, 200001)$.

Sample Input 3

2 3
998244353 998244853

Sample Output 3

3

We need three moves - for example, $(2, 3) \rightarrow (3, 3) \rightarrow (-247, 253) \rightarrow (998244353, 998244853)$.

Sample Input 4

1 1
1 1

Sample Output 4

0