Sinh viên Luna vừa nhập học K21 của IUH để học Công nghệ thông tin. Sau các buổi training về code C++, bạn rất hứng thú với các thuật toán sắp xếp mảng một chiều. Trong một ngày mưa, bạn đã sáng tạo ra cách sắp xếp khá thú vị sau đây cho mảng các số nguyên dương:

• Các số ở vị trí chia ~3~ dư ~1~ phải đổi về index chia 3 dư 1, đồng thời chúng được sắp xếp tăng dần.

• Các số ở vị trí chia ~3~ dư ~2~ phải đổi về index chia 3 dư 2, đồng thời chúng được sắp xếp giảm dần.

• Với các số chia hết cho ~3~ phải đổi về index chia hết cho 3, đồng thời giữ nguyên thứ tự xuất hiện của chúng như ban đầu.

Tuy nhiên, đôi khi mảng ban đầu không đạt được điều kiện sắp xếp trên hoặc mảng có kích thước rất lớn và điều này không dễ để thực hiện. Bạn hãy giúp Luna sắp xếp cho kịp trước khi trời mưa to nữa nhé.

Input

Dòng đầu tiên gồm số nguyên dương ~n~ với ~1 \le n \le 10^5.~ Dòng tiếp theo là giá trị của các số ~a_1, a_2, ..., a_n~ của mảng với ~1 \le a_i \le 10^9.~ Các số này không nhất thiết phân biệt.

Output

Nếu không sắp xếp được thì in ra ~-1~. Còn nếu được thì in ra mảng đã sắp xếp theo ý tưởng của Luna.

Sample input 1

6
4 5 6 1 2 3

Sample output 1

1 5 6 4 2 3

Sample input 2

4
1 2 2 1

Sample output 2

-1

Sample input 3

9
9 6 3 4 1 4 2 8 8

Sample output 3

1 8 9 4 8 6 4 2 3

Giải thích

Trong Ví dụ 1, ta thấy rằng các số chia ~3~ dư ~1~ là ~1, 4~ phải được sắp xếp tăng dần nên ~a_1 = 1, a_4 = 4,~ các số chia ~3~ dư ~2~ thì xếp giảm dần nên ~a_2 = 5, a_5 = 2~, còn lại ta giữ nguyên thứ tự xuất hiện của ~6, 3~ nên ~a_3=6, a_6=3~.

Trong Ví dụ 2, ta có thể chứng minh được rằng không có cách sắp xếp nào thỏa mãn.