Genetic Code

The links between mathematics and biology are subtle. They rarely follow the neat correspondences one might expect at first glance; instead they are abstract and not always easy to establish.

Lake Vostok — roughly 14000 square kilometers in area, up to 650 meters deep, and buried under 3743 meters of ice — was discovered beneath the Antarctic continent. For several million years it stayed under great pressure and complete darkness. It is believed that life there evolved into a more efficient form whose genetic code uses only three bases instead of four. Until proper names are agreed upon, the three bases are written as N, O, and P.

The genome is single-stranded and directed, so we may treat it as a string over the alphabet {N, O, P}. To remain stable, a genome must be a Thue sequence, named after the Norwegian mathematician A. Thue (1863–1922). Call any contiguous block of the string a subsegment, and call two subsegments adjacent when one comes immediately after the other. A Thue sequence is a string in which no two adjacent subsegments are equal — equivalently, it contains no substring of the form $WW$. For example, NOPNO is a Thue sequence, while NOPNPNO is not (its block PNPN is two equal adjacent subsegments PN and PN).

To simulate experiments with these genomes, you must generate genomes of given lengths.

The input contains several test cases. Each test case is a single integer $n$ with $1 \le n \le 5000$. The list ends with a line containing $0$, which is not processed.

Many genomes of a given length may exist, so output one canonical genome. Define the Thue genome $T$ as the fixed point of the substitution

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

started from the single base $N$: apply all three replacements simultaneously and repeat; the string stabilizes to one infinite square-free sequence whose first bases are $N\,O\,P\,N\,P\,O\,N\,O\,P\,O\,\dots$

For each test case, print on its own line the first $n$ bases of $T$. Because $T$ is a Thue sequence, every prefix of it is again a Thue sequence, so a valid genome exists for every $n \ge 1$ and each output line is non-empty.