#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pair<int, int> > vii;
#define rrep(i, m, n) for(int (i)=(m); (i)<(n);  (i)++)
#define erep(i, m, n) for(int (i)=(m); (i)<=(n); (i)++)
#define  rep(i, n)    for(int (i)=0; (i)<(n);  (i)++)
#define rrev(i, m, n) for(int (i)=(n)-1; (i)>=(m); (i)--)
#define erev(i, m, n) for(int (i)=(n); (i)>=(m); (i)--)
#define  rev(i, n)    for(int (i)=(n)-1; (i)>=0; (i)--)
#define vrep(i, c)    for(__typeof((c).begin())i=(c).begin(); i!=(c).end(); i++)
#define  ALL(v)       (v).begin(), (v).end()
#define pb            push_back
#define mp            make_pair
template<class T, class S> inline bool minup(T& m, const S x){ return m>(T)x ? (m=(T)x, true) : false; }
template<class T, class S> inline bool maxup(T& m, const S x){ return m<(T)x ? (m=(T)x, true) : false; }

static const int    INF = 2000000000;
static const ll     MOD = 1000000007LL;
static const double EPS = 1E-10;

int N, n, m;
int A[111];
int B[111];
int c[111];
int v;

inline void rotate(int m)
{
  int t = A[0];
  rep(i, m - 1) A[i] = A[i + 1];
  A[m - 1] = t;
}

int main(int argc, char *argv[])
{
  cin >> N;
  rep(i, N) cin >> A[i];
  rep(i, N) if(A[i] < 100) c[A[i]] += 1;
  rep(i, N) if(A[i] > 4) m += 1;
  
  sort(A, A + N, [&](const int& x, const int& y){
      if(x == 0){
        if(y == 0) return false;
        if(y == 1) return true;
        return false;
      }
      if(x == 1){
        if(y == 1) return false;
        if(y == 0) return false;
        return false;
      }
      if(y <= 1) return true;
      return x < y;
    });
  
  rep(i, N - 1) if(A[i] != A[i + 1]) v += 1;
  
  bool ok = true;
  if(c[2]){
    if(c[3] == 1 && (c[4] == 0 && m == 0 && (!(c[0] & 1) || c[1]))){
      swap(A[c[2]], A[c[2] - 1]);
      ok = false;
    }
    else if(c[3] == 1 && (c[4] == 0 && m == 0 && (!(c[0] & 1) || c[2] >= 2))){
      swap(A[c[2]], A[c[2] - 1]);
      //if(c[0] == 1) ok = false;
    }
    else if(c[3] == 1 && c[4] + m == 1 && (c[0] & 1)){
      swap(A[c[2]], A[c[2] - 1]);
      ok = false;
    }
    else if(c[3] == 2 && c[4] + m == 0 && ((c[0] & 1) && !c[1])){
      swap(A[c[2] + 1], A[c[2] - 1]);
      ok = false;
    }
  }
  
  else if(c[2] == 1 && !c[3]){
    if(c[4] == 1 && m == 0 && (c[0] & 1)){
      swap(A[c[2]], A[c[2] - 1]);  
        ok = false;
    }
  }
    
  if((c[0] & 1) && c[1]){
    rev(i, N - 1) if(A[i + 1] == 1 && A[i] == 0){
      swap(A[i + 1], A[i]);
      break;
    }
  }
  
  else if(ok && (c[0] == 1)){
    rotate(N - c[0]);
    //    swap(A[0], A[N - c[0] - 1]);
  }

  else if(ok && (c[0] >= 3 && (c[0] & 1))){
    rotate(N - c[0]);
    swap(A[N - c[0] - 1], A[N - 2]);
  }
  
  rep(i, N) cout << A[i] << endl;

  
  return 0;
}
### Prompt

Your challenge is to write a cpp solution to the following problem:

Training is indispensable for achieving good results at ICPC. Rabbit wants to win at ICPC, so he decided to practice today as well.

Today's training is to perform a very large number of calculations to improve the calculation power and raise awareness. Exponentiation is an operation that easily produces large numbers.

There are N non-negative integers A1, A2, ..., AN. We would like to find the sorts B1, B2, ..., BN that maximize B1B2 ... BN -1BN. Of course, it is common sense for rabbits, but this calculation is performed in order from the upper right. We also promise that 00 = 1.

There may be multiple types of B1, B2, ..., and BN that satisfy the maximum conditions. In such a case, let's choose the smallest column in the dictionary order.



Input


N
A1
...
AN


Satisfy 1 ≤ N ≤ 100, 0 ≤ Ai ≤ 1,000,000,000.

Output

The output consists of N lines. Output Bi on line i.

Examples

Input

4
7
5
10
6


Output

5
6
7
10


Input

3
0
0
1000000000


Output

1000000000
0
0

### Response

```cpp
#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pair<int, int> > vii;
#define rrep(i, m, n) for(int (i)=(m); (i)<(n);  (i)++)
#define erep(i, m, n) for(int (i)=(m); (i)<=(n); (i)++)
#define  rep(i, n)    for(int (i)=0; (i)<(n);  (i)++)
#define rrev(i, m, n) for(int (i)=(n)-1; (i)>=(m); (i)--)
#define erev(i, m, n) for(int (i)=(n); (i)>=(m); (i)--)
#define  rev(i, n)    for(int (i)=(n)-1; (i)>=0; (i)--)
#define vrep(i, c)    for(__typeof((c).begin())i=(c).begin(); i!=(c).end(); i++)
#define  ALL(v)       (v).begin(), (v).end()
#define pb            push_back
#define mp            make_pair
template<class T, class S> inline bool minup(T& m, const S x){ return m>(T)x ? (m=(T)x, true) : false; }
template<class T, class S> inline bool maxup(T& m, const S x){ return m<(T)x ? (m=(T)x, true) : false; }

static const int    INF = 2000000000;
static const ll     MOD = 1000000007LL;
static const double EPS = 1E-10;

int N, n, m;
int A[111];
int B[111];
int c[111];
int v;

inline void rotate(int m)
{
  int t = A[0];
  rep(i, m - 1) A[i] = A[i + 1];
  A[m - 1] = t;
}

int main(int argc, char *argv[])
{
  cin >> N;
  rep(i, N) cin >> A[i];
  rep(i, N) if(A[i] < 100) c[A[i]] += 1;
  rep(i, N) if(A[i] > 4) m += 1;
  
  sort(A, A + N, [&](const int& x, const int& y){
      if(x == 0){
        if(y == 0) return false;
        if(y == 1) return true;
        return false;
      }
      if(x == 1){
        if(y == 1) return false;
        if(y == 0) return false;
        return false;
      }
      if(y <= 1) return true;
      return x < y;
    });
  
  rep(i, N - 1) if(A[i] != A[i + 1]) v += 1;
  
  bool ok = true;
  if(c[2]){
    if(c[3] == 1 && (c[4] == 0 && m == 0 && (!(c[0] & 1) || c[1]))){
      swap(A[c[2]], A[c[2] - 1]);
      ok = false;
    }
    else if(c[3] == 1 && (c[4] == 0 && m == 0 && (!(c[0] & 1) || c[2] >= 2))){
      swap(A[c[2]], A[c[2] - 1]);
      //if(c[0] == 1) ok = false;
    }
    else if(c[3] == 1 && c[4] + m == 1 && (c[0] & 1)){
      swap(A[c[2]], A[c[2] - 1]);
      ok = false;
    }
    else if(c[3] == 2 && c[4] + m == 0 && ((c[0] & 1) && !c[1])){
      swap(A[c[2] + 1], A[c[2] - 1]);
      ok = false;
    }
  }
  
  else if(c[2] == 1 && !c[3]){
    if(c[4] == 1 && m == 0 && (c[0] & 1)){
      swap(A[c[2]], A[c[2] - 1]);  
        ok = false;
    }
  }
    
  if((c[0] & 1) && c[1]){
    rev(i, N - 1) if(A[i + 1] == 1 && A[i] == 0){
      swap(A[i + 1], A[i]);
      break;
    }
  }
  
  else if(ok && (c[0] == 1)){
    rotate(N - c[0]);
    //    swap(A[0], A[N - c[0] - 1]);
  }

  else if(ok && (c[0] >= 3 && (c[0] & 1))){
    rotate(N - c[0]);
    swap(A[N - c[0] - 1], A[N - 2]);
  }
  
  rep(i, N) cout << A[i] << endl;

  
  return 0;
}
```