Hãy sắp xếp dãy số gồm ~n~ phần tử ~A = \{a_1, a_2, \ldots, a_n\}~ với yêu cầu là số chẵn sắp trước, số lẻ sắp sau và tăng dần.

Input

Dòng đầu tiên chứa số nguyên dương ~n~ thỏa ~1 \le n \le 3000~.

Dòng tiếp theo chứa các số nguyên ~a_i~ thỏa ~1 \le a_i \le 10^9~.

Output

In ra dãy được sắp theo yêu cầu.

Samples

Sample Input 1

5
2 3 1 4 5

Sample Output 1

2 4 1 3 5