#include<bits/stdc++.h>
using namespace std;
 
int N;
 
void mk_one(int zc,int oc){
  if( zc%2 == 0 ){//0 is even
    for(int i=0;i<zc;i++) cout << 0 << endl;
    for(int i=0;i<oc;i++) cout << 1 << endl;
  } else {// 0 is odd
    for(int i=0;i<zc-1;i++) cout << 0 << endl;
    if( oc-- ) cout << 1 << endl;
    cout << 0 << endl;
    for(int i=0;i<oc;i++) cout << 1 << endl;
  }
}
 
void mk_one2(int zc,int oc,int a){
  if( zc%2 == 0 ){//0 is even
    for(int i=0;i<zc;i++) cout << 0 << endl;
    for(int i=0;i<oc;i++) cout << 1 << endl;
    cout << a << endl;
  } else {// 0 is odd
    for(int i=0;i<zc-1;i++) cout << 0 << endl;
    bool f = false;
    if( oc == 0 ){
      cout << a << endl;
      f = true;
    } else{
      cout << 1 << endl;
      oc--;
    }
    cout << 0 << endl;
    for(int i=0;i<oc;i++) cout << 1 << endl;
    if( !f ) cout << a << endl;
  }
}
 
void mk_A(int zc,int oc,const vector<int>& A){
  cout << A[0] << endl;
  mk_one(zc,oc);
}
 
void mk_A2(int zc,int oc,const vector<int>& A){
  cout << max(A[0],A[1]) << endl;
  mk_one2(zc,oc,min(A[0],A[1]));
}
 
void mk_large(int zc,int oc,vector<int> A){
  sort(A.begin(),A.end());
   
  int ga = -1;
  if( zc%2==1 && oc==0 ){
    ga = A[0];
    A.erase(A.begin());
  }
 
  int n = A.size();
  if( A[n-2] == 2 &&  A[n-1] == 3 ){ 
    swap(A[n-2],A[n-1]);
  }
 
  for(int i=0;i<n;i++) cout << A[i] << endl;
 
  if( ga == -1 ){
    mk_one(zc,oc);
  } else {
    mk_one2(zc,oc,ga);
  }
 
}
 
int main(){
  vector<int> A;
  int zc = 0,oc = 0;
  cin >> N;
  for(int i=0;i<N;i++){
    int x; cin >> x;
    if( x>1 ) A.push_back(x);
    else if( x == 1 ){
      oc++;
    } else
      zc++;
  }
 
  if( zc == N ){//ALL0
    for(int i=0;i<N;i++) cout << 0 << endl;
  } else if( A.size()==0 || (A.size() == 1 && zc%2==1 && oc==0) ){
    //??????1?????????
    if( A.size() == 0 ){//0 or 1 only
      mk_one(zc,oc);
    } else { // 0 or 1 and X
      mk_one2(zc,oc,A[0]);
    }
  } else if( (A.size()==1 && (oc>=1 || zc%2==0) ) ||
         (A.size()==2 && oc==0 && zc%2==1 ) ){
    //??????A[0or1]?????????
    if(A.size()==1 && (oc>=1 || zc%2==0) ){
      mk_A(zc,oc,A);
    } else {
      mk_A2(zc,oc,A);
    }
  } else {
    //??????????????????
    mk_large(zc,oc,A);
  }
   
   
 
}
### Prompt

Your task is to create 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;
 
int N;
 
void mk_one(int zc,int oc){
  if( zc%2 == 0 ){//0 is even
    for(int i=0;i<zc;i++) cout << 0 << endl;
    for(int i=0;i<oc;i++) cout << 1 << endl;
  } else {// 0 is odd
    for(int i=0;i<zc-1;i++) cout << 0 << endl;
    if( oc-- ) cout << 1 << endl;
    cout << 0 << endl;
    for(int i=0;i<oc;i++) cout << 1 << endl;
  }
}
 
void mk_one2(int zc,int oc,int a){
  if( zc%2 == 0 ){//0 is even
    for(int i=0;i<zc;i++) cout << 0 << endl;
    for(int i=0;i<oc;i++) cout << 1 << endl;
    cout << a << endl;
  } else {// 0 is odd
    for(int i=0;i<zc-1;i++) cout << 0 << endl;
    bool f = false;
    if( oc == 0 ){
      cout << a << endl;
      f = true;
    } else{
      cout << 1 << endl;
      oc--;
    }
    cout << 0 << endl;
    for(int i=0;i<oc;i++) cout << 1 << endl;
    if( !f ) cout << a << endl;
  }
}
 
void mk_A(int zc,int oc,const vector<int>& A){
  cout << A[0] << endl;
  mk_one(zc,oc);
}
 
void mk_A2(int zc,int oc,const vector<int>& A){
  cout << max(A[0],A[1]) << endl;
  mk_one2(zc,oc,min(A[0],A[1]));
}
 
void mk_large(int zc,int oc,vector<int> A){
  sort(A.begin(),A.end());
   
  int ga = -1;
  if( zc%2==1 && oc==0 ){
    ga = A[0];
    A.erase(A.begin());
  }
 
  int n = A.size();
  if( A[n-2] == 2 &&  A[n-1] == 3 ){ 
    swap(A[n-2],A[n-1]);
  }
 
  for(int i=0;i<n;i++) cout << A[i] << endl;
 
  if( ga == -1 ){
    mk_one(zc,oc);
  } else {
    mk_one2(zc,oc,ga);
  }
 
}
 
int main(){
  vector<int> A;
  int zc = 0,oc = 0;
  cin >> N;
  for(int i=0;i<N;i++){
    int x; cin >> x;
    if( x>1 ) A.push_back(x);
    else if( x == 1 ){
      oc++;
    } else
      zc++;
  }
 
  if( zc == N ){//ALL0
    for(int i=0;i<N;i++) cout << 0 << endl;
  } else if( A.size()==0 || (A.size() == 1 && zc%2==1 && oc==0) ){
    //??????1?????????
    if( A.size() == 0 ){//0 or 1 only
      mk_one(zc,oc);
    } else { // 0 or 1 and X
      mk_one2(zc,oc,A[0]);
    }
  } else if( (A.size()==1 && (oc>=1 || zc%2==0) ) ||
         (A.size()==2 && oc==0 && zc%2==1 ) ){
    //??????A[0or1]?????????
    if(A.size()==1 && (oc>=1 || zc%2==0) ){
      mk_A(zc,oc,A);
    } else {
      mk_A2(zc,oc,A);
    }
  } else {
    //??????????????????
    mk_large(zc,oc,A);
  }
   
   
 
}
```