Peano Curve Distance

A Peano curve is a continuous curve that passes through every cell of a square grid. In the 1^st–order case the curve is drawn on a 3×3 grid. It starts at the bottom‐left cell (coordinate (0,0)) and ends at the top–right cell (coordinate (2,2)). Its visiting order is as follows:

Step 0: (0,0)
Step 1: (0,1)
Step 2: (0,2)
Step 3: (1,2)
Step 4: (1,1)
Step 5: (1,0)
Step 6: (2,0)
Step 7: (2,1)
Step 8: (2,2)

For higher‐order Peano curves (of order k), the curve is defined on a grid of size \(3^k \times 3^k\) with the following corner coordinates:

• Bottom–left: (0,0)
• Bottom–right: (3^k−1, 0)
• Top–left: (0, 3^k−1)
• Top–right: (3^k−1, 3^k−1)

The k–order curve is obtained by replacing every cell of the 1^st–order curve with a suitably scaled copy of the entire 1^st–order curve. Although the exact geometric transformation (rotations/reflections) is somewhat involved, one can show that a digit–decomposition approach works. In particular, one may define a function pos(k, x, y) which returns the visiting index (starting from 0 up to \(9^k-1\)) of the cell at coordinate \( (x,y) \) on the k–order Peano curve.

For the 1^st–order curve the mapping is defined by the following 3×3 table P (where the coordinate system has (0,0) at the bottom–left):

P[0][0] = 0,   P[0][1] = 1,   P[0][2] = 2
P[1][0] = 5,   P[1][1] = 4,   P[1][2] = 3
P[2][0] = 6,   P[2][1] = 7,   P[2][2] = 8

Then for k > 1 we define

[ \text{pos}(k,x,y)= P[ b_x ][ b_y ] \times (m^2) + \text{pos}(k-1, x\bmod m, y\bmod m), \quad m=3^{k-1}, \quad b_x=\lfloor x/m \rfloor, b_y=\lfloor y/m \rfloor. ]

Given two points on the Peano curve (which are guaranteed to lie on the curve), the distance along the curve is defined as the absolute difference of their visiting indices.

Your task is: Given an integer k and two points’ coordinates on the k^th–order Peano curve, compute the distance along the curve between these two points.

inputFormat

The input consists of a single line containing five integers: k x1 y1 x2 y2. Here, k (1 ≤ k ≤ 10) denotes the order of the Peano curve; x1 y1 and x2 y2 are the coordinates of the two points on the curve. It is guaranteed that the points lie on the k^th–order Peano curve. (Recall that the grid has size \(3^k \times 3^k\) and its corners are at (0,0), (3^k−1,0), (0,3^k−1) and (3^k−1,3^k−1)).

outputFormat

Output a single integer – the distance between the two given points along the Peano curve, which is the absolute difference of their visiting indices.

sample

1 0 0 2 2

8