Description

给你一个数 $n$，你需要求出一个长度为 $n$ 的数组 $a$，（下标从 $1$ 开始，且元素都为 $1,2,3$ 或 $4$），使得：

• 对于第 $i$ 个数，对于所有的 $1 \le len \le \lfloor\frac{i}{2}\rfloor$, $a_{i-len+1\dots i}$ 与 $a_{i-len\times2+1\dots i-len}$ 不相同。（$\lfloor x \rfloor$ 表示对 $x$ 下取整）

• 说人话，就是没有任何连续的连续子串相同。

Input Format

一行一个正整数 $n$。

Output Format

一行，$n$ 个正整数，数组 $a$。

3

1 2 3

6

1 2 3 4 1 3

Hint

对于 $20\%$ 的数据，满足 $1 \le n \le 10$；

对于 $40\%$ 的数据，满足 $1 \le n \le 30$；

对于 $100\%$ 的数据，满足 $1 \le n \le 500$。