Array Not Divisible by Three

Given an array of positive integers, reorder all numbers so that the sum of every pair of adjacent numbers is not divisible by 3.

If several valid orders exist, print any one of them. Every given number must be used exactly once.

The first line contains the size of the array, N. (1 <= N <= 10000)

The second line contains N positive integers separated by spaces. Each integer is at most 1000000.

If the array can be reordered as required, print one valid reordered array on one line.

If it is impossible, print -1.