#include<bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;++i)
#define in(v,n) v.push_back(n)
using namespace std;
int n,p1,p2,q,t,a[101],x;
int main(){
  vector<int>v;
  cin>>n;
  r(i,n)cin>>a[i];
  sort(a,a+n);
  r(i,n)if(!a[i])p1++;
   else if(a[i]==1)p2++;
  if(p1%2&&p2){
    r(i,n){
      if(a[i]>1)in(v,a[i]);
    }
    r(i,n)if(!a[i])if(t++)in(v,0);
    in(v,1);t=0;in(v,0);
    r(i,n)if(a[i]==1)if(t++)in(v,1);
    if(p1!=1)p1++;
  }
  else if(p1%2&&!p2){
    r(i,n){
      if(a[i]>1&&!q)q=a[i];
      else if(a[i]>1&&q)in(v,a[i]);
    }
    r(i,n)if(!a[i])if(t++)in(v,0);
    if(q)in(v,q);
    in(v,0);if(p1!=1)p1++;
  }
  else{
    r(i,n)if(a[i]>1)in(v,a[i]);
    r(i,n)if(!a[i])in(v,0);
    r(i,n)if(a[i]==1)in(v,1);
  }
  for(int i=v.size()-1;i>=0;i--){
    if(v[i]<2)continue;
    if(i!=v.size()-1&&v[i+1]==0&&p1%2||i!=0&&v[i-1]==0)continue;
    if(i>0&&v[i]==3&&v[i-1]==2)swap(v[i],v[i-1]);
    break;
  }
  r(i,v.size())cout<<v[i]<<endl;
}
### Prompt

Please create a solution in cpp 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>
#define r(i,n) for(int i=0;i<n;++i)
#define in(v,n) v.push_back(n)
using namespace std;
int n,p1,p2,q,t,a[101],x;
int main(){
  vector<int>v;
  cin>>n;
  r(i,n)cin>>a[i];
  sort(a,a+n);
  r(i,n)if(!a[i])p1++;
   else if(a[i]==1)p2++;
  if(p1%2&&p2){
    r(i,n){
      if(a[i]>1)in(v,a[i]);
    }
    r(i,n)if(!a[i])if(t++)in(v,0);
    in(v,1);t=0;in(v,0);
    r(i,n)if(a[i]==1)if(t++)in(v,1);
    if(p1!=1)p1++;
  }
  else if(p1%2&&!p2){
    r(i,n){
      if(a[i]>1&&!q)q=a[i];
      else if(a[i]>1&&q)in(v,a[i]);
    }
    r(i,n)if(!a[i])if(t++)in(v,0);
    if(q)in(v,q);
    in(v,0);if(p1!=1)p1++;
  }
  else{
    r(i,n)if(a[i]>1)in(v,a[i]);
    r(i,n)if(!a[i])in(v,0);
    r(i,n)if(a[i]==1)in(v,1);
  }
  for(int i=v.size()-1;i>=0;i--){
    if(v[i]<2)continue;
    if(i!=v.size()-1&&v[i+1]==0&&p1%2||i!=0&&v[i-1]==0)continue;
    if(i>0&&v[i]==3&&v[i-1]==2)swap(v[i],v[i-1]);
    break;
  }
  r(i,v.size())cout<<v[i]<<endl;
}
```