You're given an array a of length n

. You can perform the following operation on it as many times as you want:

  • Pick two integers i

and j (1≤i,j≤n) such that ai+aj is odd, then swap ai and aj

  • .

What is lexicographically the smallest array you can obtain?

An array x

is lexicographically smaller than an array y if there exists an index i such that xi<yi, and xj=yj for all 1≤j<i. Less formally, at the first index i in which they differ, xi<yi

 

Input

The first line contains an integer n

(1≤n≤105) — the number of elements in the array a

.

The second line contains n

space-separated integers a1, a2, …, an (1≤ai≤109) — the elements of the array a

.

Output

The only line contains n

space-separated integers, the lexicographically smallest array you can obtain.

Examples

Input

Copy

3
4 1 7

Output

Copy

1 4 7

Input

Copy

2
1 1

Output

Copy

1 1

Note

In the first example, we can swap 1

and 4 since 1+4=5, which is odd.

思路：如果只有奇数或者偶数，输出原数组，否则排序再输出

#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define Max 105
#include<queue>
int a[105000];
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int x=0,y=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            if(a[i]%2==1) x++;
            else y++;
        }
        if((x==n)||(y==n))
        {
            printf("%d",a[1]);
            for(int i=2;i<=n;i++)
            {
                printf(" %d",a[i]);
            }
        }
        else
        {
            sort(a+1,a+n+1);
            printf("%d",a[1]);
            for(int i=2;i<=n;i++)
            {
                printf(" %d",a[i]);
            }
        }
        printf("\n");
    }
}