Cho mảng ~A~ gồm ~N~ số nguyên. In ra các số chẵn theo thứ tự không giảm, sau đó in ra các số lẻ theo thứ tự không giảm.

Input

• Dòng 1: chứa ~2~ số nguyên ~N~ (~N \leq 5000~).
• Dòng 2: chứa ~N~ số nguyên ~A_i \leq 10^9~.

Output

In ra yêu cầu đề bài.

Sample Test

Input:

7
2 5 6 1 3 2 3

Output:

2 2 6 1 3 3 5