You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

[ABC184C] Super Ryuma

注：本题不设置部分分！

题面翻译

有一个无限大的棋盘，棋盘上有一只超级马，超级马从棋盘上的点 $(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)$ 的最少步数。

输入格式

第一行两个整数 $r_1,c_1$ ，第二行两个整数 $r_2,c_2$ 。

输出格式

一个整数表示答案。

样例 #1

样例输入 #1

1 1
5 6

样例输出 #1

2

样例 #2

样例输入 #2

1 1
1 200001

样例输出 #2

2

样例 #3

样例输入 #3

2 3
998244353 998244853

样例输出 #3

3

样例 #4

样例输入 #4

1 1
1 1

样例输出 #4

0

数据范围

• $1\ \le\ r_1,\ c_1,\ r_2,\ c_2\ \le\ 10^9$

样例解释 1

$(1,\ 1)\ \rightarrow\ (5,\ 5)\ \rightarrow\ (5,\ 6)$ 。

样例解释 2

$(1,\ 1)\ \rightarrow\ (100001,\ 100001)\ \rightarrow\ (1,\ 200001)$ 。

样例解释 3

$(2,\ 3)\ \rightarrow\ (3,\ 3)\ \rightarrow\ (-247,\ 253)\ \rightarrow\ (998244353,\ 998244853)$ 。