유전 부호

수학과 생물학의 연결 고리는 미묘하다. 언뜻 보이는 깔끔한 대응을 따르는 경우는 드물며, 대개는 추상적이고 쉽게 밝혀지지도 않는다.

남극 대륙 아래에서 보스토크 호수가 발견되었다. 넓이는 약 14000제곱킬로미터, 깊이는 최대 650미터이며, 3743미터 두께의 얼음에 덮여 있다. 이 호수는 수백만 년 동안 높은 압력과 완전한 어둠 속에 있었다. 그곳의 생명은 더 효율적인 형태로 진화하여, 네 개가 아닌 세 개의 염기만으로 이루어진 유전 부호를 사용한다고 여겨진다. 적절한 이름이 정해지기 전까지 세 염기를 각각 N, O, P 로 표기한다.

유전체(genome)는 한 가닥이며 방향이 있으므로, 알파벳 {N, O, P} 위의 문자열로 볼 수 있다. 안정적으로 유지되려면 유전체는 노르웨이 수학자 A. Thue(1863–1922)의 이름을 딴 Thue 수열이어야 한다. 문자열에서 연속한 구간을 부분구간이라 하고, 한 부분구간이 다른 부분구간 바로 뒤에 이어질 때 두 부분구간이 인접한다고 하자. Thue 수열이란 인접한 두 부분구간이 서로 같은 경우가 전혀 없는 문자열이다(즉 $WW$ 꼴의 부분문자열을 포함하지 않는다). 예를 들어 NOPNO 는 Thue 수열이지만, NOPNPNO 는 아니다(부분문자열 PNPN 이 서로 같은 인접 부분구간 PN 과 PN 으로 이루어져 있다).

이 유전체로 실험을 모의하기 위해, 주어진 길이의 유전체를 생성하여라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 정수 $n$ 하나이며 $1 \le n \le 5000$ 이다. 마지막 테스트 케이스 다음에는 $0$ 이 한 줄에 주어지며, 이 값은 처리하지 않는다.

같은 길이의 유전체는 여러 개 존재할 수 있으므로, 정해진 하나를 출력한다. Thue 유전체 $T$ 를 다음 치환의 고정점으로 정의한다.

$$N \to NOP, \qquad O \to NP, \qquad P \to O$$

한 개의 염기 $N$ 에서 시작하여 세 규칙을 동시에 적용하는 과정을 반복하면 문자열은 하나의 무한 제곱 없는(square-free) 수열로 수렴한다. 그 앞부분은 $N,O,P,N,P,O,N,O,P,O,\dots$ 이다.

각 테스트 케이스마다 $T$ 의 앞에서부터 $n$ 개의 염기를 한 줄에 출력한다. $T$ 는 Thue 수열이므로 그 모든 접두사도 Thue 수열이다. 따라서 모든 $n \ge 1$ 에 대해 유효한 유전체가 존재하며, 각 출력 줄은 비어 있지 않다.