#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)n; ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cout<<*i<<" "; cout<<endl; }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
string memo[101][101][2];
string rec(int x, int y, int z){
  if(memo[x][y][z] != "U") return memo[x][y][z];
  if(x < 0 || y < 0) assert(false);
  if(x == 0 && y == 0) assert(false);
  if(x == 0){
    if(z == 0) return "Z";
    return memo[x][y][z] = string(y, '1');
  }
  if(y == 0){
    if(x % 2 == 1 && z == 0) return memo[x][y][z] = string(x, '0');
    if(x % 2 == 0 && z == 1) return memo[x][y][z] = string(x, '0');
    return memo[x][y][z] = "Z";
  }
  if(z == 0){
    string res = "0" + rec(x - 1, y, 1);
    if(res[res.size() - 1] == 'Z') return memo[x][y][z] = "Z";
    return memo[x][y][z] = res;
  }else{
    string s = "Z";
    if(rec(x - 1, y , 0) != "Z") s = min(s, "0" + rec(x - 1, y, 0));
    if(rec(x, y - 1, 0) != "Z") s = min(s, "1" + rec(x, y - 1, 0));
    if(rec(x, y - 1, 1) != "Z") s = min(s, "1" + rec(x, y - 1, 1));
    if(s[s.size() - 1] == 'Z') s = "Z";
    memo[x][y][z] = s;
    return s;
  }
}
string itos(int n){
  stringstream ss;
  ss<<n;
  return ss.str();
}

int main(){
  int N;
  REP(y, 101)REP(x, 101)REP(z, 2) memo[x][y][z] = "U";
  while(cin>>N){
    vector<int> a;
    int c0 = 0, c1 = 0;
    REP(i, N){
      int t; cin>>t;
      if(t == 0) c0++;
      else if(t == 1) c1++;
      else a.push_back(t);
    }
    sort(a.begin(), a.end());
    string s = "";
    if(c0 + c1 > 0) s = rec(c0, c1, 1);
    if(s == "Z"){
      if(a.size() > 0){
        s = string(c0 - 1, '0') + itos(a[0]) + "0";
        a.erase(a.begin());
        if(a.size() >=  2 && a[a.size() - 2] == 2 && a[a.size() - 1] == 3) swap(a[a.size() - 2], a[a.size() - 1]);
      }else{
        s = string(c0, '0');
      }
      REP(i, a.size()) cout<<a[i]<<endl;
      REP(i, s.size()) cout<<s[i]<<endl;
    }else{
      if(a.size() >= 2 && a[a.size() - 2] == 2 && a[a.size() - 1] == 3) swap(a[a.size() - 2], a[a.size() - 1]);
      REP(i, a.size()) cout<<a[i]<<endl;
      REP(i, s.size()) cout<<s[i]<<endl;
    }
  }
  return 0;
}
### Prompt

Create a solution in CPP for 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 <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)n; ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cout<<*i<<" "; cout<<endl; }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
string memo[101][101][2];
string rec(int x, int y, int z){
  if(memo[x][y][z] != "U") return memo[x][y][z];
  if(x < 0 || y < 0) assert(false);
  if(x == 0 && y == 0) assert(false);
  if(x == 0){
    if(z == 0) return "Z";
    return memo[x][y][z] = string(y, '1');
  }
  if(y == 0){
    if(x % 2 == 1 && z == 0) return memo[x][y][z] = string(x, '0');
    if(x % 2 == 0 && z == 1) return memo[x][y][z] = string(x, '0');
    return memo[x][y][z] = "Z";
  }
  if(z == 0){
    string res = "0" + rec(x - 1, y, 1);
    if(res[res.size() - 1] == 'Z') return memo[x][y][z] = "Z";
    return memo[x][y][z] = res;
  }else{
    string s = "Z";
    if(rec(x - 1, y , 0) != "Z") s = min(s, "0" + rec(x - 1, y, 0));
    if(rec(x, y - 1, 0) != "Z") s = min(s, "1" + rec(x, y - 1, 0));
    if(rec(x, y - 1, 1) != "Z") s = min(s, "1" + rec(x, y - 1, 1));
    if(s[s.size() - 1] == 'Z') s = "Z";
    memo[x][y][z] = s;
    return s;
  }
}
string itos(int n){
  stringstream ss;
  ss<<n;
  return ss.str();
}

int main(){
  int N;
  REP(y, 101)REP(x, 101)REP(z, 2) memo[x][y][z] = "U";
  while(cin>>N){
    vector<int> a;
    int c0 = 0, c1 = 0;
    REP(i, N){
      int t; cin>>t;
      if(t == 0) c0++;
      else if(t == 1) c1++;
      else a.push_back(t);
    }
    sort(a.begin(), a.end());
    string s = "";
    if(c0 + c1 > 0) s = rec(c0, c1, 1);
    if(s == "Z"){
      if(a.size() > 0){
        s = string(c0 - 1, '0') + itos(a[0]) + "0";
        a.erase(a.begin());
        if(a.size() >=  2 && a[a.size() - 2] == 2 && a[a.size() - 1] == 3) swap(a[a.size() - 2], a[a.size() - 1]);
      }else{
        s = string(c0, '0');
      }
      REP(i, a.size()) cout<<a[i]<<endl;
      REP(i, s.size()) cout<<s[i]<<endl;
    }else{
      if(a.size() >= 2 && a[a.size() - 2] == 2 && a[a.size() - 1] == 3) swap(a[a.size() - 2], a[a.size() - 1]);
      REP(i, a.size()) cout<<a[i]<<endl;
      REP(i, s.size()) cout<<s[i]<<endl;
    }
  }
  return 0;
}
```