Problem: Boy Dima gave Julian a birthday present — set B consisting of positive integers. However, he didn't know, that Julian hates sets, but enjoys bipartite graphs more than anything else!

Julian was almost upset, but her friend Alex said, that he can build an undirected graph using this set in such a way: let all integer numbers be vertices, then connect any two i and j with an edge if |i - j| belongs to B.

Unfortunately, Julian doesn't like the graph, that was built using B. Alex decided to rectify the situation, so he wants to erase some numbers from B, so that graph built using the new set is bipartite. The difficulty of this task is that the graph, Alex has to work with, has an infinite number of vertices and edges! It is impossible to solve this task alone, so Alex asks you for help. Write a program that erases a subset of minimum size from B so that graph constructed on the new set is bipartite.

Recall, that graph is bipartite if all its vertices can be divided into two disjoint sets such that every edge connects a vertex from different sets.

Input

First line contains an integer n ~ (1 ⩽ n ⩽ 200 000) — size of B

Second line contains n integers b_1, b_2, …, b_n ~ (1 ⩽ b_i ⩽ 10^{18}) — numbers of B, all b_i are unique

Output

In the first line print single integer k – the number of erased elements. In the second line print k integers — values of erased elements.

If there are multiple answers, print any of them.

Examples

Input


3
1 2 3


Output


1
2 

Input


2
2 6


Output


0

Solution (in JAVA):

Solution:
import java.util.*;
import java.math.*;

// **** D. Alex and Julian ****

public class D {
	static char [] in = new char [1000005];
	public static void main (String [] arg) throws Throwable {
		int n = nextInt();
		long [] B = new long [n];
		
		for (int i = 0; i<n; ++i) B[i] = nextLong();
		boolean [] removed = new boolean [n];
		int best_ans = 0;
		StringBuilder b = new StringBuilder(1);
		int removedcnt = 0;
		
		while (removedcnt < n) {
			//System.err.println("terating with " + removedcnt + " removed");
			long g = 0;
			int odd = 0;
			int even = 0;
			for (int i = 0; i<n; ++i)
				if (!removed[i]) 
					g = (g == 0) ? B[i] : ((g == 1) ? 1 : gcdL(g, B[i]));
		
			for (int i = 0; i<n; ++i) {
				if (!removed[i]) {
					long B2 = B[i]/g;
					if (B2 % 2 == 1) odd++;
					else even++;
				}
			}
			if (odd > best_ans) {
				best_ans = odd;
				//System.err.println("Best Answer is " + best_ans);
				b = new StringBuilder((removedcnt+even)*18);
				for (int i = 0; i<n; ++i) {
					if (removed[i] || (B[i] / g) % 2 == 0) {
						b = b.append(B[i]);
						b = b.append(' ');
					}
				}
			}
			if (odd >= even || even<best_ans) break;
				for (int i = 0; i<n; ++i) 
					if (!removed[i] && (B[i] / g) % 2 == 1) {
						removed[i] = true;
						removedcnt++;
					}
			
			
		}
		System.out.println(n - best_ans);
		System.out.println(b);
		
	}

	
	
	
	
	
	
	
	
	
	
	
	
	
	/************** HELPER CLASSES ***************/
    //static class HS extends HashSet<Integer>{public HS(){super();}public HS(int a){super(a);}};
	//static class AL extends ArrayList<Integer>{public AL(){super();}public AL(int a){super (a);}};
	static class Pair implements Comparable<Pair> {
		int i,j;long L; public Pair(int xx, int yy, long LL){i=xx;j=yy;L=LL;} 
		public int compareTo(Pair p) { return (this.L < p.L) ? -1 : (this.L == p.L) ? this.i - p.i : 1;}
	}
	/************** FAST IO CODE FOLLOWS *****************/
	public static long nextLong() throws Throwable {
		long i = System.in.read();boolean neg = false;while (i < 33) i = System.in.read();if (i == 45) {neg=true;i=48;}i = i - 48;
		int j = System.in.read();while (j > 32) {i*=10;i+=j-48;j = System.in.read();}return (neg) ? -i : i;
	}
	public static int nextInt() throws Throwable {return (int)nextLong();}
	public static String next() throws Throwable {
		int i = 0; while (i < 33 && i != -1) i = System.in.read(); int cptr = 0; while (i >= 33) { in[cptr++] = (char)i; i = System.in.read();}
		return new String(in, 0,cptr);
	}
	/**** LIBRARIES ****/
	public static long gcdL(long a, long b) {while (b != 0) {long tmp = b;b = (a % b);a = tmp;}return a;}
	public static int gcd(int a, int b) {while (b != 0) {int tmp = b;b = (a % b);a = tmp;}return a;}
	public static int[] sieve(int LIM) {
		int i,count = 0;
		boolean [] b = new boolean [LIM];
		for (i = 2;i<LIM; ++i) if (!b[i]) {count++; for (int j = i<<1; j<LIM; j+=i) b[j] = true;}
		int [] primes = new int[count];
		for (i = 2,count=0;i<LIM;++i) if (!b[i]) primes[count++] = i;
		return primes;
	}
	public static int[] numPrimeFactors(int LIM) {
		int i,count = 0;
		int [] b = new int [LIM];
		for (i = 2;i<LIM; ++i) if (b[i] == 0) {count++; for (int j = i; j<LIM; j+=i) b[j]++;}
		return b;
	}
	public static StringBuilder stringFromArray(int [] a) {
		StringBuilder b = new StringBuilder(9*a.length);
		for (int i = 0; i<a.length; ++i) {
			if (i != 0) b = b.append(' ');
			b = b.append(a[i]);
		}
		return b;
	}
	public static long modPow (long a, long n, long MOD) { long S = 1; for (;n > 0; n>>=1, a=(a*a)%MOD) if ((n & 1) != 0) S = (a*S) % MOD; return S;}
}

/* Full Problem Text:
  
Boy Dima gave Julian a birthday present - set B consisting of positive integers.
However, he didn't know, that Julian hates sets, but enjoys bipartite graphs more than anything else!

Julian was almost upset, but her friend Alex said, that he can build an undirected graph using this set in such way: let all integer numbers be vertices, then connect any two i and j with an edge if |i - j| belongs to B.
Unfortunately, Julian doesn't like the graph, that was built using B.
Alex decided to rectify the situation, so he wants to erase some numbers form B, so that graph built using the new set is bipartite.
The difficulty of this task is that the graph, Alex has to work with, has an infinite number of vertices and edges! It is impossible to solve this task alone, so Alex asks you for help.
Write a program that erases a subset of minimum size from B so that graph constructed on the new set is bipartite.
Recall, that graph is bipartite if all its vertices can be divided into two disjoint sets such that every edge connects a vertex from different sets.

 */