Cho một dãy số nguyên. Viết chương trình thực hiện sắp xếp dãy số theo các quy tắc như sau:

• Với mỗi vị trí, nếu ban đầu là số chẵn thì giá trị sau khi sắp xếp vẫn là số chẵn; nếu ban đầu là số lẻ thì giá trị sau khi sắp xếp vẫn là số lẻ.
• Tính từ trái qua phải: Các số chẵn được sắp xếp theo thứ tự không tăng; Các số lẻ được sắp xếp theo thứ tự không giảm.

Input Specification

• Dòng thứ nhất chứa số nguyên dương \(n\);
• Dòng thứ hai chứa dãy \(n\) số nguyên, hai số liên tiếp ngăn cách nhau bởi một dấu khoảng trắng.

Output Specification

In ra kết quả trên một dòng.

Constraints

• \(n \leq 10^4\)
• Các số trong dãy có giá trị tuyệt đối không vượt quá \(10^6\)

Input Sample

8
1 5 2 8 4 3 5 6

Output Sample

1 3 8 6 4 5 5 2

Explanation for Sample Output

Trong dãy ban đầu, nhóm các số lẻ là: (1; 5; 3; 5), sắp xếp thành (1; 3; 5; 5).
Trong dãy ban đầu, nhóm các số chẵn là: (2; 8; 4; 6), sắp xếp thành (8; 6; 4; 2).
Trộn theo quy tắc các nhóm chẵn/lẻ, ta thu được kết quả sắp xếp là 1 3 8 6 4 5 5 2.