좋은 수열

숫자 1, 2, 3만으로 이루어진 수열을 생각하자. 어떤 양의 길이에 대해 서로 이웃한 두 부분 수열이 완전히 같으면 그 수열은 나쁜 수열이다. 그런 경우가 하나도 없는 수열은 좋은 수열이다.

나쁜 수열은 다음과 같다.

• 33
• 32121323 (21이 바로 이어서 반복된다)
• 123123213 (123이 바로 이어서 반복된다)

좋은 수열은 다음과 같다.

• 2
• 32
• 32123
• 1232123

길이가 N인 좋은 수열을 N자리 정수로 보았을 때, 그중 가장 작은 수를 나타내는 수열을 구하라. 예를 들어 1213121과 2123212는 모두 좋은 수열이지만, 더 작은 수는 1213121이다.

입력은 정수 N 하나로 이루어진다. N은 1 이상 80 이하이다.

첫째 줄에 1, 2, 3만으로 이루어진 길이 N의 좋은 수열 중 가장 작은 수를 나타내는 수열을 출력한다. 수열의 숫자 사이에는 공백을 넣지 않는다.