题目描述

皮亚诺曲线是一条平面内的曲线。

下图给出了皮亚诺曲线的 1 阶情形, 它是从左下角出发, 经过一个 $3 \times 3$ 的 方格中的每一个格子, 最终到达右上角的一条曲线。

下图给出了皮亚诺曲线的 2 阶情形, 它是经过一个 $3^{2} \times 3^{2}$ 的方格中的每一 个格子的一条曲线。它是将 1 阶曲线的每个方格由 1 阶曲线替换而成。

下图给出了皮亚诺曲线的 3 阶情形, 它是经过一个 $3^{3} \times 3^{3}$ 的方格中的每一 个格子的一条曲线。它是将 2 阶曲线的每个方格由 1 阶曲线替换而成。

皮亚诺曲线总是从左下角开始出发, 最终到达右上角。

我们将这些格子放到坐标系中, 对于 $k$ 阶皮亚诺曲线, 左下角的坐标是 $(0,0)$, 右上角坐标是 $\left(3^{k}-1,3^{k}-1\right)$, 右下角坐标是 $\left(3^{k}-1,0\right)$, 左上角坐标是 $\left(0,3^{k}-1\right)$ 。

给定 $k$ 阶皮亚诺曲线上的两个点的坐标, 请问这两个点之间, 如果沿着皮 亚诺曲线走, 距离是多少?

输入格式

输入的第一行包含一个正整数 $k$, 皮亚诺曲线的阶数。

第二行包含两个整数 $x_{1}, y_{1}$, 表示第一个点的坐标。 第三行包含两个整数 $x_{2}, y_{2}$, 表示第二个点的坐标。

输出格式

输出一个整数, 表示给定的两个点之间的距离。

1
0 0
2 2

8

2
0 2
0 3

13

提示

对于 $30 \%$ 的评测用例, $0 \leq k \leq 10$ 。

对于 $50 \%$ 的评测用例, $0 \leq k \leq 20$ 。

对于所有评测用例, $0 \leq k \leq 100,0 \leq x_{1}, y_{1}, x_{2}, y_{2}<3^{k}, x_{1}, y_{1}, x_{2}, y_{2} \leq 10^{18}$ 。 数据保证答案不超过 $10^{18}$ 。

蓝桥杯 2020 年国赛 A 组 F 题（B 组 F 题, C 组 H 题）。