테스트
시간 제한2초메모리 제한256 MB
길이 n인 모든 2^n개 이진 문자열을 나열하되, 1의 개수가 감소하지 않고 인접한 두 문자열이 많아야 두 위치에서만 다르도록 한다.
문제
Артем은 전자 시스템에서 교육용 테스트를 보고 있다. 테스트 문제에는 n개의 진술이 있고, 그중 일부는 참이므로 체크박스로 표시해야 한다. 체크박스를 몇 개 선택하면 답이 맞는지 확인할 수 있다. 모든 참인 진술에 체크가 되어 있고 모든 거짓인 진술에 체크가 되어 있지 않으면 그 답은 정답으로 간주된다.
Артем은 생각하기 귀찮아서 체크박스를 놓는 모든 경우를 그냥 나열하기로 했다. 이를 위해 그는 2 * n개의 모든 체크박스 배치를 나열한 목록을 만든다. 목록에는 각 체크박스 배치가 정확히 한 번씩 있어야 한다.
직관적으로 참인 진술이 많을 것 같아서 그는 체크된 체크박스 수가 감소하는 순서로 배치를 나열하려고 한다. 게다가 Артем은 매우 게을러서 연속한 두 배치가 서로 다른 위치의 수가 2를 넘지 않기를 원한다. Артем을 도와주자.
입력
첫째 줄에 정수 n이 주어진다. (1 ≤ n ≤ 16)
출력
2 * n개의 줄을 출력한다. i번째 줄에는 i번째 답에 대한 각 체크박스의 상태를 나타내는 0 또는 1인 n개의 문자를 출력한다. 1은 체크된 상태, 0은 체크되지 않은 상태이다. 각 답에서 1의 개수는 증가하지 않아야 한다. 인접한 두 줄이 서로 다른 위치의 수는 2를 넘지 않아야 한다.