20941번 - 성싶당 스페셜 저지

최근 수현이는 빵가게 <성싶당>을 차렸다. 겉은 과자보다 바삭하고 속은 포근할 정도로 촉촉한 빵을 매일 구워 파는 성싶당은 얼마 지나지 않아 인스타 빵지순례 명소가 될 정도로 인기 베이커리가 되었지만, 안타깝게도 강화된 거리두기로 손님이 매우 줄었다.

성싶당은 시대의 흐름에 따라 배달 주문을 받기 시작했다. 빵 하나에는 $N$가지의 재료가 들어가는데, 각각의 재료는 두 가지 바리에이션이 있어서 두 가지 중 하나를 고를 수 있다. 예를 들자면, 반죽은 밀가루나 통밀가루 중 하나를 고를 수 있고, 시럽은 메이플 시럽과 딸기 시럽 중 하나를 고를 수 있는 식이다. 따라서 $2^N$종류의 빵이 만들어질 수 있다. 아니나 다를까 맙소사, 배달 첫날부터 $2^N$개의 주문이 들어왔는데 주문으로 들어온 빵의 종류가 모두 달랐다.

아무리 빵 굽기에 숙련된 수현이라도 $2^N$개의 주문을 처리하는 건 무리였다. 다행히도 성싶당의 직원들은 각자 재료 한 종류씩을 빠르게 준비할 수 있어서, 여러 직원이 한 재료씩 각자 동시에 준비하면 시간을 절약할 수 있다. 따라서 수현이는 다음 식이 최소가 되도록 주문들의 순서를 바꾸려고 한다.

$\displaystyle\sum_{i=1}^{2^N-1}$ ($i$번째 주문과 $i + 1$번째 주문에서 겹치는 재료의 종류의 수)

단, 첫 번째로 주문한 손님의 빵은 첫 번째로 만들려고 한다. $N$과 첫 번째 손님의 주문이 주어질 때, 위의 식이 최소가 되도록 하려면 주문들을 어떤 순서로 처리해야 하는지 알려주자.

다음과 같이 입력이 주어진다.

주문 $2^N$개를 $p_1$으로 시작해 한 줄에 하나씩 출력한다. 각 주문은 입력 형식과 같은 방식으로, $i$번째 문자가 $i$번째 재료의 종류가 되도록 길이 $N$의 문자열을 구성해 출력한다.

조건을 만족하는 주문 순서가 여러 개 있을 경우 그중 하나만 출력한다.

• $N$은 성싶당 빵에 들어가는 재료의 수다. ($1 \leq N \leq 20$)
• $p_1$은 첫 번째 주문을 의미하는 문자열이다. $i$번째 문자는 $i$번째 재료 종류를 의미하며, 배달 주문 시스템의 대역폭을 아끼기 위해 한 바리에이션을 0으로, 다른 바리에이션을 1로 표현한다. ($\left|c_0\right|=N$)