몽유병 환자

어떤 건물의 지붕은 한 변의 길이가 $3^k$인 정사각형 모양이며, 크기는 $3^k \times 3^k$이다. 지붕의 각 변은 동서 방향과 남북 방향에 평행하다. 지붕은 한 변의 길이가 $1$인 정사각형 타일로 덮여 있는데, 그중 한 장이 빠져서 사람이 빠질 만큼 큰 구멍이 뚫려 있다.

타일들은 직사각형 격자를 이루므로 각 타일의 위치를 좌표로 나타낼 수 있다. 남서쪽 모서리에 있는 타일의 좌표는 $(1, 1)$이다. 첫 번째 좌표는 동쪽으로 갈수록 커지고, 두 번째 좌표는 북쪽으로 갈수록 커진다.

몽유병 환자가 지붕 위를 돌아다닌다. 매 걸음마다 지금 서 있는 타일에서 동(E), 서(W), 남(S), 북(N) 중 한 방향으로 인접한 타일로 이동한다. 걷기는 항상 남서쪽 모서리 타일에서 시작한다. 이동 경로는 N, S, E, W 네 글자로 이루어진 단어 $d_k$로 나타내며, 각 글자는 그 방향으로 한 걸음 이동함을 뜻한다.

$k = 1$일 때 경로는 다음과 같다.

d_1 = EENNWSWN

$k = 2$일 때 경로는 다음과 같다.

d_2 = NNEESWSEENNEESWSEEEENNWSWNNEENNWSWNNEENNWSWNWWWSSENESSSSWWNENWWSSWWNENWNEENNWSWN

일반적으로 $k \ge 1$일 때, 크기가 $3^{k+1} \times 3^{k+1}$인 지붕 위의 경로는 $d_k$로부터 다음과 같이 만들어진다.

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

여기서 $a$, $b$, $c$는 네 방향 글자에 대한 치환이다.

어떤 함수를 단어에 적용한다는 것은 위 표의 열에 따라 각 글자를 바꾸는 것이다. 예를 들어 $a(SEN) = WNE$, $b(SEN) = ESW$, $c(SEN) = NWS$이다.

관찰은 몽유병 환자가 타일 $(u_1, u_2)$ 위에 서 있는 순간부터 시작한다. 빠진 타일 $(v_1, v_2)$ 자리에 생긴 구멍에 그가 빠지기까지 몇 걸음을 걷게 되는가?

아래 그림은 크기가 $3 \times 3$과 $9 \times 9$인 지붕 위에서의 이동 경로를 보여 준다. $9 \times 9$인 경우에는 관찰을 시작하는 타일과 구멍의 위치를 함께 표시하였다.

다음을 수행하는 프로그램을 작성하라. 지붕의 크기를 나타내는 $k$, 관찰이 시작될 때 몽유병 환자가 서 있는 타일, 그리고 구멍이 된 타일의 좌표를 입력받아, 그가 구멍에 빠지기 전까지 걷는 걸음 수를 계산하여 출력한다.

표준 입력의 첫째 줄에는 지붕의 크기 $3^k \times 3^k$를 나타내는 정수 $k$가 주어지며, $1 \le k \le 60$이다. 이어지는 두 줄에는 각각 공백으로 구분된 두 정수 $x$와 $y$가 주어지며, $1 \le x \le 3^k$, $1 \le y \le 3^k$이다. 둘째 줄의 두 수는 관찰이 시작될 때 몽유병 환자가 서 있는 타일의 좌표이고, 셋째 줄의 두 수는 구멍의 좌표이다. 주어지는 입력은 언제나 몽유병 환자가 결국 구멍에 빠지도록 보장된다.

몽유병 환자가 시작 타일에서 구멍까지 이동하는 경로의 걸음 수를 한 줄에 출력한다.