Problem Description

A Peano curve is a curve on a plane.

The figure below shows the order-$1$ Peano curve. It starts from the lower-left corner, passes through every cell in a $3 \times 3$ grid, and finally reaches the upper-right corner.

The figure below shows the order-$2$ Peano curve. It passes through every cell in a $3^{2} \times 3^{2}$ grid. It is obtained by replacing each cell of the order-$1$ curve with an order-$1$ curve.

The figure below shows the order-$3$ Peano curve. It passes through every cell in a $3^{3} \times 3^{3}$ grid. It is obtained by replacing each cell of the order-$2$ curve with an order-$1$ curve. (Note: in the picture below, the last column is missing one edge due to a drawing error.)

A Peano curve always starts from the lower-left corner and finally reaches the upper-right corner.

We place these cells in a coordinate system. For an order-$k$ Peano curve, the lower-left corner is $(0,0)$, the upper-right corner is $\left(3^{k}-1,3^{k}-1\right)$, the lower-right corner is $\left(3^{k}-1,0\right)$, and the upper-left corner is $\left(0,3^{k}-1\right)$.

Given the coordinates of two points on an order-$k$ Peano curve, what is the distance between these two points if you walk along the Peano curve?

Input Format

The first line contains a positive integer $k$, the order of the Peano curve.

The second line contains two integers $x_{1}, y_{1}$, representing the coordinates of the first point.
The third line contains two integers $x_{2}, y_{2}$, representing the coordinates of the second point.

Output Format

Output one integer, representing the distance between the given two points.

1
0 0
2 2

8

2
0 2
0 3

13

Hint

For $30\%$ of the test cases, $0 \leq k \leq 10$.

For $50\%$ of the test cases, $0 \leq k \leq 20$.

For all test cases, $0 \leq k \leq 100$, $0 \leq x_{1}, y_{1}, x_{2}, y_{2} < 3^{k}$, and $x_{1}, y_{1}, x_{2}, y_{2} \leq 10^{18}$. The testdata guarantees that the answer does not exceed $10^{18}$.

Lanqiao Cup 2020 National Finals, Group A Problem F (Group B Problem F, Group C Problem H).

Translated by ChatGPT 5