Your task is to partition the numbers 1,2,\dots,n into three sets such that the sum of the numbers in the 2nd set is one larger than that of the 1st set, and one smaller than that of the 3rd set.

Input

The only line of input contains the integer n.

Output

Print one line with n integers, g_1\ g_2\ \dots\ g_n. The number g_k expresses which of the three sets the number k is placed in.

If a solution does not exist, print IMPOSSIBLE instead.

Example 1

Input:

8

Output:

1 3 1 2 3 3 1 2

Explanation: The chosen sets are \{1,3,7\}, \{4,8\} and \{2,5,6\}, with respective sums 11, 12 and 13.

Example 2

Input:

4

Output:

IMPOSSIBLE

Subtask 1 (22 points)

• 3 \le n \le 10

Subtask 2 (78 points)

• 3 \le n \le 100