철학자의 산책로

프로그래밍 나라에는 철학자가 쉬어 가는 산책로가 여럿 있다. 철학자의 산책로는 나무가 빽빽한 정사각형 구역 안에 놓인 길이다. 나무는 철학자가 사색하는 데 도움이 되지만, 너무 촘촘하게 심어 놓은 탓에 미로처럼 되어 길을 잃는 철학자가 생긴다.

다행히 모든 철학자의 산책로는 구조가 비슷하다. 한 변이 $2^k$ 미터인 정사각형 안에 같은 규칙으로 길을 놓는다. $k$가 1이면 1미터를 걸을 때마다 오른쪽으로 90도 돈다. $k$가 1보다 크면 $k-1$짜리 산책로 네 개를 프랙털 방식으로 이어 붙인다. 그림 F.1은 $k$가 1, 2, 3일 때의 산책로다. $W_2$는 $W_1$ 네 개로 이루어지는데, 왼쪽 아래는 시계 방향으로 90도, 오른쪽 아래는 반시계 방향으로 90도 돌린 모양이고, 위쪽 둘은 $W_1$과 방향이 같다. $k$가 1보다 큰 모든 $W_k$도 마찬가지다. 이 규칙은 수학자이자 철학자인 다비트 힐베르트(1862-1943)가 고안했고, 이렇게 만들어진 길을 힐베르트 곡선이라고 부른다. 힐베르트는 한 변이 $2^k$인 정사각형을 이런 곡선으로 채우는 공간 채움 방법을 이야기한 적이 있으며, 모든 철학자의 산책로는 이 방법대로 설계한다.

(a) $W_1$	(b) $W_2$	(c) $W_3$

그림 F.1. 한 변이 (a) $2^1 = 2$, (b) $2^2 = 4$, (c) $2^3 = 8$인 철학자의 산책로 세 개.

태천이는 열기구를 타고 산책로에서 길을 잃은 철학자를 구조하는 일을 맡고 있다. 길을 잃은 철학자는 자기가 몇 미터를 걸었는지 태천이에게 알릴 수 있고, 태천이는 산책로 정사각형의 한 변 길이를 알고 있다. 태천이는 철학자가 있는 자리를 좌표 $(x, y)$로 알아내야 한다. 산책로는 1미터를 단위 길이로 하는 좌표평면의 제1사분면에 놓여 있고, 왼쪽 아래 구석 칸의 좌표는 $(1, 1)$이다. 산책로의 입구는 항상 $(1, 1)$이고 출구는 항상 $(n, 1)$이다. 여기서 $n$은 한 변의 길이다. 철학자가 입구에 있을 때 이미 1미터를 걸은 것으로 보며, 철학자는 뒤로 돌아가지 않고 출구 쪽으로 앞으로만 걷는다.

예를 들어 그림 F.1(b)의 $W_2$에서 길을 잃은 철학자가 10미터를 걸었다면 그 자리는 $(3, 4)$다.

철학자가 걸은 미터 수와 산책로 정사각형의 한 변 길이가 주어질 때, 철학자가 있는 자리를 알려 주는 프로그램을 작성하라.

입력은 한 줄이다. 양의 정수 $n$과 $m$이 공백으로 구분되어 주어진다. $n$은 철학자의 산책로 정사각형의 한 변 길이이고, $m$은 길을 잃은 철학자가 걸은 미터 수다. $n = 2^k$이고 $1 \le m \le 2^{2k}$이며, $k$는 $0 < k \le 15$인 정수다.

한 줄에 정수 두 개 $x$와 $y$를 공백으로 구분해 출력한다. $(x, y)$는 길을 잃은 철학자가 있는 자리다.