33079번 - 흑백 설곽 서브태스크점수

문제

서울과학고등학교의 연말 축제 천년제에서 싸이컴은 새로운 게임 부스를 운영하려고 한다!

게임은 $N$명의 학생들이 원탁에 앉아서 진행하는데, 다음과 같이 진행된다고 한다.

• $N$명의 학생들은 초기에 검은색 또는 흰색 모자를 쓰고 진행한다. 자신이 쓴 모자의 색은 확인할 수 없으며, 다른 $N-1$명의 학생들이 쓴 모자만을 볼 수 있다.
• 게임 중에 학생들은 서로 소통할 수 없으며, 게임 중에 자신을 포함한 모든 학생은 모두 서로를 구분하지 못한다.
• 분석 과정에서는 학생들이 본인이 아닌 원탁에 앉은 다른 $N-1$명의 학생들의 모자 색을 본인의 오른쪽부터 반시계 방향으로 한 명씩 차례대로 확인할 수 있다. 원탁에 앉은 $N-1$명의 학생들의 모자 색을 확인한 후, 자신 앞에 놓인 종이에 0ドル$ 이상 13ドル$ 미만의 정수 하나를 작성해야 한다. 학생들이 작성한 정수는 오직 $N-1$명의 다른 학생들의 모자 색에만 의존해야 한다.
• 모든 학생이 종이에 정수를 적은 후, 종이들은 원탁 중앙으로 모여 섞이고 학생들은 첫 스텝에서 경험한 모든 일에 대한 기억을 잃게 된다. 또한, 학생들의 머리에 씌워진 모자들은 벗겨진다. 이후, 학생들은 다른 학생들의 모자를 보지 못한다.
• 결정 과정에서는 학생들이 분석 과정에서 작성한 종이들을 볼 수 있다. 분석 과정에서는 본인을 제외한 $N-1$명의 학생들이 작성한 종이의 숫자들이 오름차순으로 정렬되어 보이고, 이를 토대로 첫 스텝에서 자신의 머리에 씌워진 모자의 색이 흑색인지 백색인지 결정하여야 한다.
• 만약 모든 학생이 자신의 모자 색을 올바르게 결정하였다면 모든 학생은 게임에서 승리하게 된다.
• 반면, 어떤 학생이라도 자신의 모자 색을 올바르게 결정하지 못했다면 모든 학생은 게임에서 패배한다.

분석 과정에서 적을 수 있는 정수의 수가 많을수록 전략을 이행하기 어려우므로, 분석 과정에서 적는 정수의 최댓값이 작을수록 좋다. 또한, 모든 학생은 여러분의 전략을 완전히 똑같이 사용하기로 하였다. 즉, 어떤 위치에 있는 학생이더라도, 보이는 모자 색의 배치가 같으면 같은 정수를 적기로 한 것이고, 결정 과정에서도 마찬가지로 적용된다.

게임에서 승리하기 위한 전략을 구상해 보자!

입력

첫 번째 줄에 학생의 수 $N$이 주어진다.

출력

첫 번째 줄에 작성할 정수의 종류의 수 $X$를 출력한다. 즉, 전략에서 0ドル$ 이상 $X$ 미만의 정수를 분석 과정에서 적음을 나타낸다.

두 번째 줄에 2ドル^{n-1}$개의 0ドル$ 이상 $X$ 미만의 정수를 공백으로 구분하여 출력한다. 이는 분석 과정에서 여러분이 적는 정수를 나타내는데, 정확히는 다음과 같은 전략을 말한다.

• 어떤 학생에 대해, 원탁에 앉은 다른 학생들의 모자 색은 흑색 또는 백색의 2ドル^{n-1}$가지가 있다. 흑색은 0ドル,ドル 백색은 1ドル$에 대응시킨다.
• 이를 본인의 오른쪽부터 반시계 방향 순서대로 배열하여 길이 $n-1$의 0ドル$ 또는 1ドル$로 이루어진 수열 $S$를 만들자.
• 길이 $n-1$의 0ドル$과 1ドル$로 이루어진 수열 2ドル^{n-1}$개를 사전 순*으로 정렬하여 수열들로 이루어진 배열을 만들자.
• 이 전략은 분석 과정에서 $S$와 수열 배열의 $i$번째 수열이 일치할 때, 두 번째 줄에 출력하는 $i$번째 정수를 종이에 적음을 말한다.

세 번째 줄에 $H_{X, N-1}$**개의 0ドル$ 또는 1ドル$의 정수를 공백으로 구분하여 출력한다. 이는 검증 과정에서 여러분이 결정하는 본인의 모자 색을 의미하는데, 정확한 전략은 다음과 같다.

• 원탁에 앉은 다른 학생들이 적은 종이 $N-1$개를 오름차순으로 정렬하여 본다면, 총 $H_{X, N-1}$개의 경우의 수가 존재한다.
• 종이에 적힌 $N-1$개의 수를 오름차순으로 정렬한 수열을 모아 사전 순*으로 정렬하여 길이 $H_{X, N-1}$의 수열 배열을 만들자.
• 이 전략은 분석 과정에서 종이에 적힌 수들이 수열 배열의 $i$번째 원소에 해당할 때, 세 번째 줄에 출력하는 $i$번째 정수가 0ドル$이면 본인의 모자 색을 흑색, 1ドル$이면 본인의 모자 색을 백색으로 결정한다는 것을 나타낸다.

출력은 다음의 조건을 만족해야 한다.

• $N$명의 학생들의 모자 색에 따라 2ドル^N$가지의 원탁에서의 모자 색의 배치가 가능하다.
• 가능한 모든 배치에서 여러분이 출력한 전략을 토대로 게임을 진행하였을 때, 게임에서 승리해야 한다.

* 배열을 사전 순으로 정렬한다는 것은 사전 순 비교를 통해 정렬한다는 것이고, 사전 순 비교에서는 두 수열이 앞에서부터 처음으로 다른 값을 가지는 위치에서 더 작은 값을 가진 수열이 앞선다.

** $H_{N, R}$은 0ドル$ 이상 $N$ 미만의 정수들로 이루어져 있는 길이 $R$의 오름차순 수열의 개수를 말한다.

제한

• 4ドル \le N \le 13$

서브태스크

힌트