CSES - Datatähti Open 2021 - Split in Three
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Your task is to partition the numbers 1,2,,n1,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 nn.

Output

Print one line with nn integers, g1 g2  gng_1\ g_2\ \dots\ g_n. The number gkg_k expresses which of the three sets the number kk 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}\{1,3,7\}, {4,8}\{4,8\} and {2,5,6}\{2,5,6\}, with respective sums 1111, 1212 and 1313.

Example 2

Input:

4

Output:

IMPOSSIBLE

Subtask 1 (22 points)

  • 3n103 \le n \le 10

Subtask 2 (78 points)

  • 3n1003 \le n \le 100