We're giving away nice huge bags containing number tiles! A bag we want to present to you contains n tiles. Each of them has a single number written on it — either 1 or 2.

However, there is one condition you must fulfill in order to receive the prize. You will need to put all the tiles from the bag in a sequence, in any order you wish. We will then compute the sums of all prefixes in the sequence, and then count how many of these sums are prime numbers. If you want to keep the prize, you will need to maximize the number of primes you get.

Can you win the prize? Hurry up, the bags are waiting!

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 200 000) — the number of number tiles in the bag. The following line contains n space-separated integers a_1, a_2, ..., a_n (a_i ∈ \{1, 2\}) — the values written on the tiles.

Output

Output a permutation b_1, b_2, ..., b_n of the input sequence (a_1, a_2, ..., a_n) maximizing the number of the prefix sums being prime numbers. If there are multiple optimal permutations, output any.

Examples

Input


5
1 2 1 2 1


Output


1 1 1 2 2


Input


9
1 1 2 1 1 1 2 1 1


Output


1 1 1 2 1 1 1 2 1

Note

The first solution produces the prefix sums 1, \mathbf{\color{blue}{2}}, \mathbf{\color{blue}{3}}, \mathbf{\color{blue}{5}}, \mathbf{\color{blue}{7}} (four primes constructed), while the prefix sums in the second solution are 1, \mathbf{\color{blue}{2}}, \mathbf{\color{blue}{3}}, \mathbf{\color{blue}{5}}, 6, \mathbf{\color{blue}{7}}, 8, 10, \mathbf{\color{blue}{11}} (five primes). Primes are marked bold and blue. In each of these cases, the number of produced primes is maximum possible.

import java.io.IOException;

import java.io.*;
import java.io.*;
import java.util.Iterator;

/**
 * http://codeforces.com/problemset/problem/1149/A #math #numbertheory #greedy
 * 
 * We maintain Eratosten's sieve to use for iterating over primes. Greedily
 * build the prefix sum to reach the next prime as soon as possible (take twos
 * first and then ones).
 */
public class PrefixSumPrimes {

	public static void main(String[] args) throws IOException {
		Reader r = new Reader();
		Writer w = new Writer();

		int n = r.nextInt();
		// Sieve larger than 2n (by 100k) to have spare primes to "chase".
		EratostenSieve e = new EratostenSieve(500000);

		int ones = 0;
		int twos = 0;
		for (int i = 0; i < n; ++i) {
			int a = r.nextInt();
			if (a == 1)
				ones++;
			else
				twos++;
		}

		int sum = 0;
		for (int p : e.primes(2)) {
			for (; sum < p && p - sum >= 2 && twos > 0; --twos, sum += 2)
				w.print("2 ");
			for (; sum < p && ones > 0; --ones, ++sum)
				w.print("1 ");
			if (ones == 0 && twos == 0)
				break;
		}

		w.close();
	}

}


/**
 * Custom class used for fast input.
 */
class Reader {

	final private int BUFFER_SIZE = 1 << 16;
	private DataInputStream din;
	private byte[] buffer;
	private int bufferPointer, bytesRead;

	public Reader() {
		din = new DataInputStream(System.in);
		buffer = new byte[BUFFER_SIZE];
		bufferPointer = bytesRead = 0;
	}

	public Reader(String file_name) throws IOException {
		din = new DataInputStream(new FileInputStream(file_name));
		buffer = new byte[BUFFER_SIZE];
		bufferPointer = bytesRead = 0;
	}

	public String readLine() throws IOException {
		byte[] buf = new byte[64]; // line length
		int cnt = 0, c;
		while ((c = read()) != -1) {
			if (c == '\n')
				break;
			buf[cnt++] = (byte) c;
		}
		return new String(buf, 0, cnt);
	}

	public int nextInt() throws IOException {
		int ret = 0;
		byte c = read();
		while (c <= ' ')
			c = read();
		boolean neg = (c == '-');
		if (neg)
			c = read();
		do {
			ret = ret * 10 + c - '0';
		} while ((c = read()) >= '0' && c <= '9');

		if (neg)
			return -ret;
		return ret;
	}

	public long nextLong() throws IOException {
		long ret = 0;
		byte c = read();
		while (c <= ' ')
			c = read();
		boolean neg = (c == '-');
		if (neg)
			c = read();
		do {
			ret = ret * 10 + c - '0';
		} while ((c = read()) >= '0' && c <= '9');
		if (neg)
			return -ret;
		return ret;
	}

	public double nextDouble() throws IOException {
		double ret = 0, div = 1;
		byte c = read();
		while (c <= ' ')
			c = read();
		boolean neg = (c == '-');
		if (neg)
			c = read();

		do {
			ret = ret * 10 + c - '0';
		} while ((c = read()) >= '0' && c <= '9');

		if (c == '.') {
			while ((c = read()) >= '0' && c <= '9') {
				ret += (c - '0') / (div *= 10);
			}
		}

		if (neg)
			return -ret;
		return ret;
	}

	private void fillBuffer() throws IOException {
		bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
		if (bytesRead == -1)
			buffer[0] = -1;
	}

	private byte read() throws IOException {
		if (bufferPointer == bytesRead)
			fillBuffer();
		return buffer[bufferPointer++];
	}

	public void close() throws IOException {
		if (din == null)
			return;
		din.close();
	}
}


/**
 * Custom class used for fast output.
 */
class Writer {
	private final BufferedWriter bw;

	public Writer() {
		this.bw = new BufferedWriter(new OutputStreamWriter(System.out));
	}

	public void print(Object object) throws IOException {
		bw.append("" + object);
	}

	public void println(Object object) throws IOException {
		print(object);
		bw.append("\n");
	}

	public void close() throws IOException {
		bw.close();
	}

}


/**
 * Represents the linear Eratosten's sieve for generating prime numbers. Mainly
 * used for primality tests and fast iteration over prime numbers, but can also
 * be used for fast factorization of numbers.
 */
class EratostenSieve {

	/**
	 * Internal structure of the sieve.
	 */
	private int[] sieve;

	/**
	 * Array that for each prime number points to next prime. Value is zero for last
	 * prime in the sieve and any composite.
	 */
	private int[] next;

	/**
	 * Array that for each prime number points to previous prime. Value is zero for
	 * first prime in the sieve and any composite.
	 */
	private int[] prev;

	/**
	 * Initializes the sieve of size n + 1.
	 * 
	 * Time complexity: O(nln(ln(n))), Memory complexity: O(n)
	 * 
	 * @param n Size of the sieve.
	 */
	public EratostenSieve(int n) {
		sieve = new int[n + 1];
		prev = new int[n + 1];
		next = new int[n + 1];

		sieve[0] = -1; // Zero is not prime by definition.
		sieve[1] = 0; // One is not prime by definition.
		int currPrime = 2;
		for (int i = 2; i <= n; ++i) {
			if (sieve[i] == 0) {
				for (int j = i; j <= n; j += i)
					sieve[j] = i;
				if (currPrime != i) {
					next[currPrime] = i;
					prev[i] = currPrime;
					currPrime = i;
				}
			}
		}
	}

	/**
	 * Determines if a given positive whole number is prime.
	 * 
	 * Time complexity: O(1), Memory complexity: O(1)
	 * 
	 * @param x Positive whole number.
	 * @return True if given number is prime, otherwise false.
	 */
	public boolean isPrime(int x) {
		return sieve[x] == x;
	}

	/**
	 * Calculates largest prime factor of the given number.
	 * 
	 * Time complexity: O(1), Memory complexity: O(1)
	 * 
	 * @param x Positive whole number.
	 * @return Largest prime factor.
	 */
	public int primeFactor(int x) {
		return sieve[x];
	}

	/**
	 * Calculates first prime number in the sieve larger than p. Zero will be
	 * returned in case the given number is not prime or it is the last prime number
	 * in the sieve.
	 * 
	 * Time complexity: O(1), Memory complexity: O(1)
	 * 
	 * @param p Prime number.
	 * @return Next prime number larger than given prime, or zero.
	 */
	public int nextPrime(int p) {
		return next[p];
	}

	/**
	 * Calculates first prime number in the sieve smaller than p. Zero will be
	 * returned in case the given number is not prime or it is the first prime
	 * number in the sieve.
	 * 
	 * Time complexity: O(1), Memory complexity: O(1)
	 * 
	 * @param p Prime number.
	 * @return First prime number smaller than given prime, or zero.
	 */
	public int prevPrime(int p) {
		return prev[p];
	}

	/**
	 * Gives the size of the sieve.
	 * 
	 * Time complexity: O(1), Memory complexity: O(1)
	 * 
	 * @return Size of the sieve.
	 */
	public int size() {
		return sieve.length;
	}

	public Iterable<Integer> primes(int p) {
		return new PrimeIterator(this);
	}

	public Iterable<Integer> factors(int n) {
		return new FactorIterator(this, n);
	}

	/**
	 * Base class for various iterators over Eratosten's sieve.
	 */
	private abstract class SieveIterator implements Iterable<Integer>, Iterator<Integer> {
		/**
		 * Eretosten's sieve used for iteration.
		 */
		protected EratostenSieve sieve;

		/**
		 * Number used as index for the sieve iterator.
		 */
		int number;

		/**
		 * Initializates the iterator with sieve data structure and initial number
		 * index.
		 * 
		 * @param sieve  Eratosten's sieve used for iteration.
		 * @param number Starting number index of the iterator.
		 */
		public SieveIterator(EratostenSieve sieve, int number) {
			this.sieve = sieve;
			this.number = number;
		}

		public Iterator<Integer> iterator() {
			return this;
		}
	}

	/**
	 * Iterator for iterating over prime factors of given positive integer, in
	 * descending order.
	 */
	private class FactorIterator extends SieveIterator {
		/**
		 * Initializes iterator with given number and sieve.
		 * 
		 * @param sieve  Eretosten's sieve used for factorization.
		 * @param number Positive whole number that is factorized.
		 */
		public FactorIterator(EratostenSieve sieve, int number) {
			super(sieve, number);
		}

		public boolean hasNext() {
			return number > 1;
		}

		public Integer next() {
			int factor = sieve.primeFactor(number);
			number /= factor;
			return factor;
		}
	}

	/**
	 * Prime number iterator used for iterating over primes in ascending order,
	 * starting from given prime number.
	 */
	private class PrimeIterator extends SieveIterator {
		/**
		 * Initializes prime number iterator starting from 2.
		 * 
		 * @param sieve Eratosten's sieve used when iterating.
		 */
		public PrimeIterator(EratostenSieve sieve) {
			this(sieve, 2);
		}

		/**
		 * Initializes prime number iterator starting from given prime.
		 * 
		 * @param prime Initial prime number.
		 * @param sieve Eratosten's sieve used when iterating.
		 */
		public PrimeIterator(EratostenSieve sieve, int prime) {
			super(sieve, prime);
		}

		public boolean hasNext() {
			return number < sieve.size() && sieve.nextPrime(number) != 0;
		}

		public Integer next() {
			number = sieve.nextPrime(number);
			return sieve.prevPrime(number);
		}
	}
}
