샤워실 바닥 깔기 (Large)

오늘은 민규가 훈련소에 입소하는 날이다. 행사를 모두 마치고 생활관에서 쉬려는데 교관이 들어와 민규를 불렀다. 따라갔더니 김준서를 아느냐고 물었다. 그 녀석이 샤워실 바닥을 깔면서 배수구 자리까지 막아 버렸으니, 같은 학교 출신인 민규가 바닥을 다시 깔라는 것이었다.

샤워실 바닥은 정사각형이고 한 변의 길이는 2의 거듭제곱이다. 준서는 $2 \times 2$ 크기의 타일로 바닥을 전부 채웠는데, 이렇게 채우면 배수구가 놓일 칸을 비울 수 없다. 대신 세 칸을 차지하는 ㄱ자 모양 타일을 쓰면 배수구 칸 하나만 남기고 바닥을 모두 덮을 수 있다. ㄱ자 타일은 $2 \times 2$ 정사각형에서 한 칸을 뺀 모양이고, 네 방향 중 어느 쪽으로든 돌려서 놓을 수 있다.

배수구 칸을 뺀 모든 칸을 ㄱ자 타일로 겹치지 않게 덮는 배치를 구하라.

첫째 줄에 바닥의 크기를 정하는 자연수 $K$ $(1 \le K \le 7)$가 주어진다. 바닥의 한 변의 길이는 $2^K$이다.

둘째 줄에 배수구의 위치를 나타내는 자연수 $x$, $y$ $(1 \le x, y \le 2^K)$가 공백으로 구분되어 주어진다. 가장 왼쪽 아래 칸이 $(1, 1)$, 가장 오른쪽 위 칸이 $(2^K, 2^K)$이다.

바닥의 배치도를 $2^K$줄에 걸쳐 출력한다. 첫 줄이 $y = 2^K$인 행이고 마지막 줄이 $y = 1$인 행이다. 각 줄에는 $x = 1$부터 $x = 2^K$까지의 칸을 공백 하나로 구분해 출력한다. 배수구가 있는 칸은 $-1$로, 나머지 칸은 그 칸을 덮는 타일의 번호로 적는다.

배치하는 방법은 여러 가지이므로 다음 규칙으로 답 하나를 정한다. 이 규칙을 그대로 따른 배치만 정답으로 인정한다.

타일은 다음 재귀 규칙으로 놓는다.

• 한 변의 길이가 $1$인 정사각형에는 배수구 칸만 있으므로 타일을 놓지 않는다.
• 한 변의 길이가 $2^k$ $(k \ge 1)$인 정사각형은 한 변의 길이가 $2^{k-1}$인 사분면 네 개로 나눈다. 이 정사각형의 중심에 닿는 칸이 각 사분면마다 하나씩 있는데, 배수구가 들어 있지 않은 세 사분면의 그 칸 세 개를 ㄱ자 타일 하나로 덮는다. 그다음 방금 덮은 칸 세 개를 각각 자기 사분면의 배수구로 보고, 사분면 네 개에 같은 규칙을 다시 적용한다.

타일 번호는 배치가 모두 끝난 뒤에 매긴다. $y$가 작은 행부터 훑고 같은 행에서는 $x$가 작은 칸부터 훑으면서, 아직 번호가 없는 타일을 만날 때마다 $1$, $2$, $3$, ... 을 차례로 붙인다.

$1 \le K \le 7$에서 이 배치는 항상 존재하고, 타일 번호는 $19000$을 넘지 않는다.