### COCI 2008/2009, Contest #6

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".

```3
1 2 3```

`2 3 1`

```5
4 6 3 9 8```

### Output

`3 4 6 8 9`

```6
3 7 6 4 2 8```

### Output

`3 7 4 6 2 8`

```3
3 12 9```

### Output

`impossible`

Point Value: 10
Time Limit: 1.00s
Memory Limit: 32M

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

• (0/0)
What's wrong with my 30/100 program?

• (0/0)
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.

• (0/2)
whats the input for that?

• (5/0)
14 followed by some permutation of {1, 4, 1, 7, 0, 4, 8, 2, 5, 5, 8, 2, 2, 5}

• (0/0)
seems to work on my computer :\

• (0/0)
cant there be difference outputs?

• (0/0)
Sure - that's why this problem has a custom judge.