39수열

미쿠미쿠하게 해줄게♪ 세상 속 그 누구, 누구보다도

— ika_mo, 「미쿠미쿠하게 해줄게♪」

아래 조건들을 모두 만족하는 수열을 길이가 $N$인 39수열이라고 하자.

• 수열은 $N$개의 정수로 이루어져 있으며, 각 값은 $1$ 이상 $10^8$ 이하이다.
• 수열의 인접한 두 수를 순서를 바꾸지 않고 좌우로 이어붙여 만들 수 있는 모든 수는 $39$의 배수이다.

예를 들어 수열 $[3, 9, 75]$는 $39$와 $975$가 모두 $39$의 배수이므로 길이가 $3$인 39수열이다. 길이가 $N$인 39수열을 아무거나 하나 구해보자.

주어진 제약 조건 내에서 길이가 $N$인 39수열은 항상 존재함을 증명할 수 있다.

첫 번째 줄에 정수 $N$이 주어진다. $(2 \leq N \leq 10\,000)$

첫 번째 줄에 길이가 $N$인 39수열을 나타내는 $N$개의 정수를 공백을 사이에 두고 출력한다.

가능한 정답이 여러 개인 경우 그 중 아무거나 하나 출력한다.