cuskija

프로그램 명: coci_cuskija(special judge)

제한시간: 1 초

인접한 두 수의 합이 3 으로 나누어지지 않게 주어지는 수열을 재 배치 하시오. 불가능하다면 "impossible" 을 출력하고 여러개가 존재 한다면 그 중 하나를 출력.

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

The first line contains an integer N (1 ≤ N ≤ 10000), 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 1000000.

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 

출력 

3 4 6 8 9 

입력 

6 
3 7 6 4 2 8 

출력 

3 7 4 6 2 8 

입력 

3 
3 12 9 

출력 

impossible

출처: coci 2008/2009 contest6 4/6