- Time limit: 1.00 s
- Memory limit: 512 MB
Your task is to partition the numbers 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 .
Output
Print one line with integers, . The number expresses which of the three sets the number 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 , and , with respective sums , and .
Example 2
Input:
4
Output:
IMPOSSIBLE