Sleepwalker

A building has a flat, square roof of size $3^k \times 3^k$, with its sides parallel to the north-south and east-west directions. The roof is covered with unit square tiles (each of side length $1$), but one tile has been removed, leaving a hole large enough to fall through.

The tiles form a rectangular grid, so each tile has integer coordinates. The tile in the southwestern corner has coordinates $(1, 1)$. The first coordinate increases toward the east, and the second increases toward the north.

A sleepwalker wanders across the roof. In each step he moves from the tile he stands on to an adjacent tile: east (E), west (W), south (S), or north (N). His walk always starts from the southwestern corner tile. The walk is described by a word $d_k$ over the letters N, S, E, W, where each letter denotes one step in that direction.

For $k = 1$ the walk is:

d_1 = EENNWSWN

For $k = 2$ the walk is:

d_2 = NNEESWSEENNEESWSEEEENNWSWNNEENNWSWNNEENNWSWNWWWSSENESSSSWWNENWWSSWWNENWNEENNWSWN

In general, for $k \ge 1$, the walk on a roof of size $3^{k+1} \times 3^{k+1}$ is built from the walk $d_k$ as follows:

d_{k+1} = a(d_k) E a(d_k) E d_k N d_k N d_k W c(d_k) S b(d_k) W b(d_k) N d_k

Here $a$, $b$, and $c$ are permutations of the four direction letters:

Applying a function to a word rewrites every letter according to its column in the table above. For example, $a(SEN) = WNE$, $b(SEN) = ESW$, and $c(SEN) = NWS$.

We begin watching the sleepwalker at the moment he stands on the tile $(u_1, u_2)$. After how many steps will he fall into the hole left by the removed tile at $(v_1, v_2)$?

The pictures below show the sleepwalker's path on roofs of size $3 \times 3$ and $9 \times 9$. In the $9 \times 9$ case, the tile where the observation begins and the hole are both marked.

Write a program that reads the roof size $k$, the tile where the sleepwalker stands when the observation begins, and the tile that was removed to make the hole, then computes and prints how many steps the sleepwalker takes before falling into the hole.

The first line contains one integer $k$ with $1 \le k \le 60$, giving the roof size $3^k \times 3^k$. Each of the next two lines contains two integers $x$ and $y$ separated by a space, with $1 \le x \le 3^k$ and $1 \le y \le 3^k$. The two numbers on the second line are the coordinates of the tile on which the sleepwalker stands when the observation begins. The two numbers on the third line are the coordinates of the hole. The input is guaranteed to be such that the sleepwalker eventually falls into the hole.

Print a single line containing the number of steps on the sleepwalker's path from the starting tile to the hole.