Description

You are given an integer $n$. You need to construct an array $a$ of length $n$ (indices start from $1$, and each element is one of $1,2,3$ or $4$), such that:

• For the $i$-th element, for all $1 \le len \le \lfloor\frac{i}{2}\rfloor$, the subarray $a_{i-len+1\dots i}$ is not equal to $a_{i-len\times2+1\dots i-len}$. ($\lfloor x \rfloor$ means rounding $x$ down.)

• In plain words, there are no two adjacent consecutive substrings that are identical.

Input Format

One line with one positive integer $n$.

Output Format

One line with $n$ positive integers, the array $a$.

3

1 2 3

6

1 2 3 4 1 3

Hint

For $20\%$ of the testdata, $1 \le n \le 10$.

For $40\%$ of the testdata, $1 \le n \le 30$.

For $100\%$ of the testdata, $1 \le n \le 500$.

Translated by ChatGPT 5