COCI 2008/2009, Contest #6

Task CUSKIJA

Rearrange the given array of integers so that the sum of two adjacent elements is never divisible by three.

Input

The first line contains an integer N (1 ≤ N ≤ 10,000), the number of elements in the array.
The second line contains the elements of the array separated by single spaces. The elements will be positive integers less than 1,000,000.

Output

If any valid rearrangement exists, output it on a single line. Otherwise, output "impossible".

Examples

Input

3
1 2 3

Output

2 3 1

Input

5
4 6 3 9 8

Output

3 4 6 8 9

Input

6
3 7 6 4 2 8

Output

3 7 4 6 2 8

Input

3
3 12 9

Output

impossible

All Submissions
Best Solutions


Point Value: 10
Time Limit: 1.00s
Memory Limit: 32M
Added: Mar 09, 2009

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

What's wrong with my 30/100 program?

Here's one of your outputs:
1_4_1_7_0_4_8_2_5_5_8_2_2_5__
However, the sum of 4 and 8 is divisible by 3, so it's wrong.

whats the input for that?

14 followed by some permutation of {1, 4, 1, 7, 0, 4, 8, 2, 5, 5, 8, 2, 2, 5} tongue.gif

seems to work on my computer :\

cant there be difference outputs?

Sure - that's why this problem has a custom judge.