베네시 네트워크 라우팅

컴퓨터 클러스터를 위한 상호연결 네트워크를 설계한다. 이 네트워크는 $2n-1$개의 행으로 이루어진 스위치 격자이며, 각 행에는 $2^{n-1}$개의 스위치가 있다. 하나의 스위치에는 두 개의 입력 선 $X$, $Y$와 두 개의 출력 선 $X'$, $Y'$가 있다. 스위치가 꺼짐 상태이면 입력 $X$는 출력 $X'$로, 입력 $Y$는 출력 $Y'$로 전달된다. 켜짐 상태이면 $X$가 $Y'$에, $Y$가 $X'$에 연결된다. 서로 다른 두 출발지의 데이터는 같은 선을 절대 공유할 수 없지만, 두 메시지가 한 스위치의 서로 다른 두 입력을 통해 지나가는 것은 허용된다.

맨 위 행에 $2^n$개의 컴퓨터가, 맨 아래 행에 $2^n$개의 컴퓨터가 있으며, 각 행의 컴퓨터는 왼쪽에서 오른쪽으로 $0$부터 $2^n-1$까지 번호가 매겨진다. 각 아래 행 컴퓨터가 연결되어야 하는 위 행 컴퓨터가 주어지며, 이 모든 연결이 서로 선을 공유하지 않는 경로로 동시에 이루어지도록 모든 스위치의 상태를 정해야 한다.

네트워크는 베네시(Beneš) 위상을 사용한다. $1$-베네시 네트워크는 스위치 하나이다. $n>1$이면 $n$-베네시 네트워크는 다음과 같이 재귀적으로 구성된다.

• 첫(맨 위) 행에는 $2^{n-1}$개의 스위치가 있고, 스위치 $j$($0 \le j < 2^{n-1}$)는 컴퓨터 $2j$와 $2j+1$로부터 두 입력을 받는다.
• 첫 행의 출력 선과 둘째 행의 입력 선은 완전 셔플 순열로 연결된다. 즉 어떤 행의 출력 번호 $j$는 다음 행의 입력 번호 $j'$에 연결되며, $j'$은 $j$의 $n$비트 이진 표현을 오른쪽으로 한 칸 회전시켜 얻는다. 한 행의 선은 왼쪽에서 오른쪽으로 번호가 매겨진다.
• $n>2$이면 둘째 행부터 끝에서 둘째 행까지의 행들이 두 개의 $(n-1)$-베네시 부분망을 이루며, 하나는 그 행들의 왼쪽 절반을, 다른 하나는 오른쪽 절반을 차지한다.
• 마지막으로 부분망의 출력에 역 셔플 순열을 적용하고, $2^{n-1}$개의 스위치로 이루어진 마지막 행을 덧붙인다.

입력에는 여러 개의 테스트 케이스가 있다. 각 테스트 케이스는 정수 $n$($1 \le n \le 13$)이 담긴 줄로 시작하며, 이는 연결해야 할 컴퓨터 쌍이 $2^n$개임을 뜻한다. $n=0$인 줄은 입력의 끝을 나타내며 처리하지 않는다.

$n>0$인 각 줄 다음에는 $2^n$개의 정수가 담긴 줄이 하나 더 온다. 이 중 $i$번째 정수($0 \le i < 2^n$)는 $i$번째 아래 행 컴퓨터가 통신해야 하는 위 행 컴퓨터이다. 주어지는 데이터에는 항상 유효한 스위치 설정이 최소 하나 존재한다.

각 테스트 케이스에 대해 $2n-1$개의 줄을 출력한다. 각 줄은 길이가 $2^{n-1}$인 이진 문자열로, 각 스위치가 켜짐(1)인지 꺼짐(0)인지를 나타낸다.

가능한 설정이 여러 개이면 사전순으로 가장 작은 것을 출력한다. 즉 맨 위 행의 문자열이 사전순으로 가장 작아야 하고, 같을 경우 둘째 행의 문자열이 사전순으로 가장 작아야 하며, 이런 식으로 계속한다.

연속한 테스트 케이스의 출력 사이는 빈 줄로 구분한다.