## COCI '08 Contest 6 #4 Cuskija

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

#### Input Specification

The first line contains an integer , 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 .

#### Output Specification

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

.

#### Sample Input 1

```
3
1 2 3
```

#### Sample Output 1

`2 3 1`

#### Sample Input 2

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

#### Sample Output 2

`3 4 6 8 9`

#### Sample Input 3

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

#### Sample Output 3

`3 7 4 6 2 8`

#### Sample Input 4

```
3
3 12 9
```

#### Sample Output 4

`impossible`

## Comments