CF45G.Prime Problem

In Berland prime numbers are fashionable — the respectable citizens dwell only on the floors with numbers that are prime numbers. The numismatists value particularly high the coins with prime nominal values. All the prime days are announced holidays!

Yet even this is not enough to make the Berland people happy. On the main street of the capital stand n houses, numbered from 1 to n. The government decided to paint every house a color so that the sum of the numbers of the houses painted every color is a prime number.

However it turned out that not all the citizens approve of this decision — many of them protest because they don't want many colored houses on the capital's main street. That's why it is decided to use the minimal possible number of colors. The houses don't have to be painted consecutively, but every one of n houses should be painted some color. The one-colored houses should not stand consecutively, any way of painting is acceptable.

There are no more than 5 hours left before the start of painting, help the government find the way when the sum of house numbers for every color is a prime number and the number of used colors is minimal.

在贝尔兰，素数非常流行——体面的市民只居住在楼层编号为素数的楼层上。钱币收藏家尤其看重面值为素数的硬币。所有素数日期均被宣布为假日！

然而，这仍不足以让贝尔兰人民感到幸福。首都主街上矗立着 $n$ 座房屋，编号从 $1$ 到 $n$。政府决定给每座房屋涂上一种颜色，使得每种颜色所涂房屋的编号之和均为素数。

但事实证明，并非所有市民都赞成这一决定——许多人因不愿看到首都主街上出现过多彩色房屋而提出抗议。因此，最终决定使用尽可能少的颜色数量。房屋无需连续涂色，但 $n$ 座房屋中的每一座都必须被涂上某种颜色。同色房屋不可相邻（即不允许连续出现相同颜色的房屋），其余任何涂色方式均可接受。

距离开始涂色仅剩最多 5 小时，请帮助政府找到一种方案：使得每种颜色所涂房屋的编号之和均为素数，且所用颜色数量最少。

The single input line contains an integer n (2 ≤ n ≤ 6000) — the number of houses on the main streets of the capital.

单行输入包含一个整数 $n$（$2 ≤ n ≤ 6000$）——首都主干道上的房屋数量。

Print the sequence of n numbers, where the i-th number stands for the number of color for house number i. Number the colors consecutively starting from 1. Any painting order is allowed. If there are several solutions to that problem, print any of them. If there's no such way of painting print the single number -1.

输出一个包含 n 个数字的序列，其中第 i 个数字表示第 i 座房子所涂的颜色编号。颜色编号从 1 开始连续编号。任意一种合法的涂色方案均可。若该问题存在多种解法，输出任意一种即可。若不存在满足条件的涂色方案，则仅输出单个数字 -1。