삼진 트리

어제 학교에서 야스는 새로운 게임을 만들었습니다. 먼저 종이 맨 위에 큰 원 하나를 그렸습니다. 그 아래에 작은 원 세 개를 그리고 각각을 위의 원과 선으로 이었습니다. 새로 그린 원마다 같은 일을 반복했습니다. 즉, 각 원 아래에 새 원 세 개를 그리고 그 원과 이었습니다. 이렇게 총 $k$개의 층을 만들면, 원이 $(3^k-1)/2$개인 완전 삼진 트리가 되고, 맨 아래 층에는 정확히 $3^{k-1}$개의 원이 있습니다.

게임 규칙은 다음과 같습니다. 각 학생은 맨 아래 줄의 원마다 $0$ 또는 $1$의 값을 하나씩 채웁니다. 더 높은 층의 원에는, 바로 아래에 연결된 세 자식 원 중에서 두 번 이상 나타난 값(즉 세 자식의 다수결 값)을 적습니다.

트리를 모두 채우면 알아맞히기 단계가 시작됩니다. 야스는 $1$부터 $3^{k-1}$까지의 수 하나를 불러 맨 아래 층의 원 하나를 가리키고, 학생은 그 원에 적힌 값을 알려줍니다. 야스가 맨 아래 원을 모두 확인하기 전에 맨 위(가장 큰) 원의 값을 말할 수 있으면 그가 이깁니다.

야스는 항상 이길 수 있는 질문 전략을 알아냈다고 자랑합니다. 당신은 이를 의심합니다. 그런 전략이 존재하지 않음을 보이기 위해, 야스의 전략이 주어졌을 때 맨 아래 원들에 $0$/$1$ 값을 배정하되, 야스가 맨 위 원의 값을 알아내려면 맨 아래 원을 하나도 빠짐없이 물어봐야만 하도록 만드는 프로그램을 작성하려 합니다.

야스는 어리석지 않습니다. 전략상 원 $x$를 물어볼 차례이더라도, 트리에서 $x$의 조상 중 하나의 값을 이미 알고 있어 그 원의 값이 필요 없다면 그는 그 질문을 건너뜁니다. 당신의 배정은 그런 지름길을 남겨서는 안 됩니다. 즉, 각 원을 물어보기 직전 순간에 그 원의 어떤 조상도 아직 값이 확정되어 있어서는 안 됩니다.

첫째 줄에 층의 수를 나타내는 정수 $k$ ($1 \le k \le 12$)가 주어집니다.

둘째 줄에는 $1$부터 $3^{k-1}$까지의 모든 정수가 어떤 순서로 나열되며, 이는 야스가 맨 아래 원들을 물어보는 순서를 나타냅니다.

야스의 질문 순서는 미리 정해져 있으므로, 그가 모든 원을 물어보게 만드는 배정은 여러 가지가 있습니다. 답을 유일하게 만들기 위해 다음 표준(canonical) 배정을 출력하세요.

맨 아래 원의 공개 시각을 야스의 질문 순서에서의 위치(0부터 시작)로 정의하고, 더 높은 원의 공개 시각은 그 부분 트리에 속한 맨 아래 원들의 공개 시각 중 최댓값으로 정의합니다. 맨 위 원에는 값 $0$을 배정합니다. 그런 다음 위에서 아래로 내려가면서, 값이 $v$로 정해진 맨 아래가 아닌 각 원에 대해 세 자식을 공개 시각이 빠른 순서로 보고, 가장 빨리 공개되는 자식에 $0$, 가운데 자식에 $1$, 가장 늦게 공개되는 자식에 $v$를 배정합니다. 이렇게 하면 모든 맨 아래 원의 값이 정해집니다.

야스가 물어보는 순서대로 맨 아래 원 $3^{k-1}$개의 값을 공백 하나로 구분해 출력하세요.