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 \leqslant n \leqslant 200\,000)$ — size of $B$

Second line contains $n$ integers $b_1, b_2, \ldots, b_n ~ (1 \leqslant b_i \leqslant 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

Difficulty: competition

Starter code:

Solutions:
n = int(input())
b = [int(x) for x in input().strip().split()]

result = {}

for x in b:
    tmp = x
    cnt = 0
    while tmp & 1 == 0:
        cnt += 1
        tmp >>= 1
    if cnt not in result:
        result[cnt] = []
    result[cnt].append(x)

res1 = max([len(result[x]) for x in result])
print(n - res1)
if n == res1:
    return

res2 = None
for x in result:
    if len(result[x]) == res1:
        res2 = x
        break

res3 = []
for x in result:
    if x != res2:
        for y in result[x]:
            res3.append(str(y))

print(' '.join(res3))


n = int(input())
B = list(map(int, input().split()))
A = []
for i in range(100):
    A.append([])
for i in B:
    x = i
    c = 0
    while x % 2 == 0:
        x //= 2
        c += 1
    A[c].append(i)
mlen = 0
f = 1
for lst in A:
    mlen = max(mlen, len(lst))
ans = []
for lst in A:
    if len(lst) == mlen and f:
        f = 0
    else:
        for x in lst:
            ans.append(x)
print(len(ans))
print(' '.join(list(map(str, ans))))


n = int(input())
l = list(map(int,input().split()))
wyk = [0] * n
for i in range(n):
	left = 0
	right = 72
	while abs(left-right) > 1:
		mid = (left+right)//2
		if l[i] % (2**mid) == 0:
			left = mid
		else:
			right = mid
	mid = (left+right)//2
	if l[i] % (2**(mid+1)) == 0:
		wyk[i] = mid+1
	else:
		wyk[i] = mid
d = {}
for i in wyk:
	d[i] = 0
for i in wyk:
	d[i] += 1
mak = -888999
faw = 0
for i in d:
	if d[i] >= mak:
		mak = d[i]
		faw = i
print(n - mak)
for i in range(n):
	if wyk[i] != faw:
		print(l[i])


import sys
from collections import Counter
readline = sys.stdin.readline

N = int(input())
A = list(map(int, readline().split()))
B = [(a&-a).bit_length() for a in A]
C = Counter(B).most_common(1)[0][0]
Ans = []
for i in range(N):
    if C != B[i]:
        Ans.append(A[i])

print(len(Ans))
if Ans:
    print(*Ans)

import math
n = int(input())
B = list(map(int,input().split())) 

def solve(B):
    odds = []
    evens = []
    for b in B:
        if b%2 == 0:
            evens.append(b)
        else:
            odds.append(b)
    if len(evens) == 0:
        # if no evens, we're gucci
        return []

    even_gcd = evens[0]
    for e in evens:
        even_gcd = math.gcd(even_gcd, e)

    even_remove = [even_gcd*x for x in solve([e//even_gcd for e in evens])]

    if len(odds) + len(even_remove) < len(evens):
        return odds+even_remove
    else:
        return evens


ans = solve(B)
print(len(ans))
if len(ans) != 0:
    print(" ".join([str(x) for x in ans]))


import sys
input = sys.stdin.readline

n=int(input())
B=list(map(int,input().split()))

ANS=[0]*65
BANS=[0]*n

for i in range(n):
    b=B[i]
    score=0
    while b%2==0:
        b//=2
        score+=1

    ANS[score]+=1
    BANS[i]=score

k=max(ANS)
ind=ANS.index(k)
print(n-k)

T=[B[i] for i in range(n) if BANS[i]!=ind]
print(*T)


#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n = I()
    s = S()
    d = defaultdict(lambda : 0)
    for i in s:
        d[i] += 1
    ans = [1]*d["n"]
    d["o"] -= d["n"]
    ans += [0]*d["o"]
    print(*ans)
    return

#B
def B():

    n = I()
    m = LIR(n)
    f = [0]*n
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            f[i] += math.log(m[i][j],10)
    F = sum(f)
    p = F/(2*(n-1))
    a = [round(10**((f[i]-p)/(n-2))) for i in range(n)]
    print(*a)
    return

#C
def C():
    s = S()
    n = len(s)
    g = [0]*n
    m = 26
    f = [set() for i in range(n)]
    f[ord(s[0])-ord("a")].add(0)
    for i in range(1,n):
        lis = set()
        k = ord(s[i])-ord("a")
        for j in range(k):
            lis |= f[j]
        for j in range(100):
            if j not in lis:
                g[i] = j
                break
        f[k].add(j)
    for i in g:
        if i == 0:
            print("Mike")
        else:
            print("Ann")
    return

#D
def D():
    n = I()
    b = LI()
    l = [i&-i for i in b]
    d = defaultdict(lambda : 0)
    for i in l:
        d[i] += 1
    m = [0,0]
    for i,j in list(d.items()):
        if m[1] < j:
            m = [i,j]
    ans = []
    for i in range(n):
        if m[0] != l[i]:
            ans.append(b[i])
    print(len(ans))
    print(*ans)
    return

#E
def E():

    return

#F
def F():

    return

#G
def G():

    return


#Solve
def __starting_point():
    D()

__starting_point()

def gns():
	return list(map(int,input().split()))
n=int(input())
ns=gns()
cnt=[0]*100
ans=0
for c in ns:
	for l in range(100):
		if c%(1<<l)==0:
			continue
		else:
			break
	l-=1
	cnt[l]+=1
m=max(cnt)
for i in range(100):
	if cnt[i]==m:
		m=i
		break

x=[]
for c in ns:
	if c%(1<<m)==0 and c%(1<<(m+1))!=0:
		continue
	x.append(c)
print(len(x))
print(' '.join(map(str,x)))


a = int(input())
l = list(map(int, input().split()))
ans = [0 for i in range(100)]
for i in l:
    n = 0
    while i % 2 == 0:
        n += 1
        i //= 2
    ans[n] += 1
k = ans.index(max(ans))
ann = []
for i in l:
    if i % (2 ** k) != 0 or i % (2 ** (k + 1)) == 0:
        ann.append(i) 
    else:
        pass  
print(len(ann))
print(*ann)

n=int(input())
a=list(map(int,input().split()))
c=0
b=[]
for i in range(n):
    k=1
    t=0
    while a[i]%k==0:
        k=k*2
        t+=1
    b.append(t)
from collections import Counter
count = Counter(b)
p=count.most_common()
x=p[0][0]
print(n-p[0][1])
for i in range(n):
    if b[i]!=x:
        print(a[i],end=" ")


n = int(input())
dists = list(map(int, input().split()))
pow2 = [[] for _ in range(64)]
Set = [0] * n
for i in range(n):
    ds = d = dists[i]
    powd = 0
    while d % 2 == 0:
        d >>= 1
        powd += 1
    pow2[powd].append(ds)
    Set[i] = powd
maxset = max(range(64), key=lambda x: len(pow2[x]))
print(n - len(pow2[maxset]))
for i in range(n):
    if Set[i] != maxset:
        print(dists[i], end=" ")


# https://codeforces.com/contest/1220/problem/D

n    = int(input())
a    = list(map(int, input().split()))

max_ = 0
ind  = -1
d    = {0:0}
mark = [0] * n

for i, x in enumerate(a):
    if x%2 == 1:
        d[0] += 1
    else:
        cnt = 0
        while x % 2 == 0:
            cnt += 1
            x  //= 2
        
        if cnt not in d:
            d[cnt] = 0
        d[cnt] += 1     
        mark[i]  = cnt
        
for k, v in d.items():
    if v > max_:
        max_ = v
        ind  = k 

remove = [a[i] for i, x in enumerate(mark) if x != ind]
print(len(remove))
print(' '.join([str(x) for x in remove]))

''' CODED WITH LOVE BY SATYAM KUMAR '''

from sys import stdin, stdout
import heapq
import cProfile, math
from collections import Counter, defaultdict, deque
from bisect import bisect_left, bisect, bisect_right
import itertools
from copy import deepcopy
from fractions import Fraction
import sys, threading
import operator as op
from functools import reduce
import sys

sys.setrecursionlimit(10 ** 6)  # max depth of recursion
threading.stack_size(2 ** 27)  # new thread will get stack of such size
fac_warm_up = False
printHeap = str()
memory_constrained = False
P = 10 ** 9 + 7


class MergeFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.num_sets = n
        self.lista = [[_] for _ in range(n)]

    def find(self, a):
        to_update = []
        while a != self.parent[a]:
            to_update.append(a)
            a = self.parent[a]
        for b in to_update:
            self.parent[b] = a
        return self.parent[a]

    def merge(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a == b:
            return
        if self.size[a] < self.size[b]:
            a, b = b, a
        self.num_sets -= 1
        self.parent[b] = a
        self.size[a] += self.size[b]
        self.lista[a] += self.lista[b]

    def set_size(self, a):
        return self.size[self.find(a)]

    def __len__(self):
        return self.num_sets


def display(string_to_print):
    stdout.write(str(string_to_print) + "\n")


def prime_factors(n):  # n**0.5 complex
    factors = dict()
    for i in range(2, math.ceil(math.sqrt(n)) + 1):
        while n % i == 0:
            if i in factors:
                factors[i] += 1
            else:
                factors[i] = 1
            n = n // i
    if n > 2:
        factors[n] = 1
    return (factors)


def all_factors(n):
    return set(reduce(list.__add__,
                      ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))


def fibonacci_modP(n, MOD):
    if n < 2: return 1
    return (cached_fn(fibonacci_modP, (n + 1) // 2, MOD) * cached_fn(fibonacci_modP, n // 2, MOD) + cached_fn(
        fibonacci_modP, (n - 1) // 2, MOD) * cached_fn(fibonacci_modP, (n - 2) // 2, MOD)) % MOD


def factorial_modP_Wilson(n, p):
    if (p <= n):
        return 0
    res = (p - 1)
    for i in range(n + 1, p):
        res = (res * cached_fn(InverseEuler, i, p)) % p
    return res


def binary(n, digits=20):
    b = bin(n)[2:]
    b = '0' * (digits - len(b)) + b
    return b


def is_prime(n):
    """Returns True if n is prime."""
    if n < 4:
        return True
    if n % 2 == 0:
        return False
    if n % 3 == 0:
        return False
    i = 5
    w = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += w
        w = 6 - w
    return True


def generate_primes(n):
    prime = [True for i in range(n + 1)]
    p = 2
    while p * p <= n:
        if prime[p]:
            for i in range(p * 2, n + 1, p):
                prime[i] = False
        p += 1
    return prime


factorial_modP = []


def warm_up_fac(MOD):
    nonlocal factorial_modP, fac_warm_up
    if fac_warm_up: return
    factorial_modP = [1 for _ in range(fac_warm_up_size + 1)]
    for i in range(2, fac_warm_up_size):
        factorial_modP[i] = (factorial_modP[i - 1] * i) % MOD
    fac_warm_up = True


def InverseEuler(n, MOD):
    return pow(n, MOD - 2, MOD)


def nCr(n, r, MOD):
    nonlocal fac_warm_up, factorial_modP
    if not fac_warm_up:
        warm_up_fac(MOD)
        fac_warm_up = True
    return (factorial_modP[n] * (
            (pow(factorial_modP[r], MOD - 2, MOD) * pow(factorial_modP[n - r], MOD - 2, MOD)) % MOD)) % MOD


def test_print(*args):
    if testingMode:
        print(args)


def display_list(list1, sep=" "):
    stdout.write(sep.join(map(str, list1)) + "\n")


def display_2D_list(li):
    for i in li:
        print(i)


def prefix_sum(li):
    sm = 0
    res = []
    for i in li:
        sm += i
        res.append(sm)
    return res


def get_int():
    return int(stdin.readline().strip())


def get_tuple():
    return list(map(int, stdin.readline().split()))


def get_list():
    return list(map(int, stdin.readline().split()))


memory = dict()


def clear_cache():
    nonlocal memory
    memory = dict()


def cached_fn(fn, *args):
    nonlocal memory
    if args in memory:
        return memory[args]
    else:
        result = fn(*args)
        memory[args] = result
        return result


def ncr(n, r):
    return math.factorial(n) / (math.factorial(n - r) * math.factorial(r))


def binary_search(i, li):
    fn = lambda x: li[x] - x // i
    x = -1
    b = len(li)
    while b >= 1:
        while b + x < len(li) and fn(b + x) > 0:  # Change this condition 2 to whatever you like
            x += b
        b = b // 2
    return x


# -------------------------------------------------------------- MAIN PROGRAM


TestCases = False
fac_warm_up_size = 10 ** 5 + 100
optimise_for_recursion = False  # Can not be used clubbed with TestCases WHen using recursive functions, use Python 3


def main():
    n = get_int()
    li = get_list()
    sets = [set() for _ in range(70)]
    for i in li:
        c = 0
        k = i
        while i%2==0:
            i = i//2
            c += 1
        sets[c].add(k)
    max_i = 0
    for index in range(70):
        if len(sets[max_i])<len(sets[index]):
            max_i = index
    uni = set()
    for i, seti in enumerate(sets):
        if i!=max_i:
            uni = uni.union(seti)
    print(len(uni))
    display_list(list(uni))
# --------------------------------------------------------------------- END=


if TestCases:
    for i in range(get_int()):
        main()
else:
    main() if not optimise_for_recursion else threading.Thread(target=main).start()


n = int(input())
a = list(map(int, input().split()))

count = [0] * 100
b = [0] * 200005
for i, v in enumerate(a):
    tot = 0
    while v % 2 == 0:
        v //= 2
        tot += 1
    count[tot] += 1
    b[i] = tot
m = max(count)
idx = count.index(m)
print(n-m)
for i in range(n):
    if b[i] != idx:
        print(a[i], end=' ')


from collections import Counter

def countbit(x):
    ans = 0
    while not (x&1):
        ans += 1
        x >>= 1
    return ans
    

n = int(input())
b = list(map(int,input().split()))

cnt = Counter()
for x in b:
    cnt[countbit(x)] += 1

mostcnt = cnt.most_common(1)
#mostcnt is list 

ans = []
for x in b:
    if countbit(x) != mostcnt[0][0]:
        ans.append(x)

print(len(ans))        
print(' '.join([str(x) for x in ans]))


n = int(input())
l = list(map(int, input().split()))
temp = []
for i in l:
    temp.append(len(bin(i & -i)[2:]))
f = [0] * (61)
for i in temp:
    f[i] += 1
cmp = f.index(max(f))
ans = []
for i in range(n):
    if temp[i] != cmp: ans.append(l[i])
print(len(ans))
print(*ans)

n = int(input())
l = list(map(int, input().split()))
temp = []
for i in l:
    temp.append(len(bin(i & -i)[2:]))
f = [0] * (61)
for i in temp:
    f[i] += 1
cmp = f.index(max(f))
ans = []
for i in range(n):
    if temp[i] != cmp: ans.append(l[i])
print(len(ans))
print(*ans)

import sys

def twoDiv(n):
    at = 0
    while n%2 == 0:
        n = n//2
        at += 1
    return at

total = int(next(sys.stdin))
nums = [int(k) for k in next(sys.stdin).split()]

comps = {}
largest = 0
for n in nums:
    k = twoDiv(n)
    if k not in comps.keys():
        comps[k] = set()
    comps[k].add(n)
    largest = max(largest, len(comps[k]))

good = -1
for c in comps:
    if len(comps[c]) == largest:
        good = c
        break
del comps[good]

ans = set()
for c in comps:
    ans = ans|comps[c]
ans = sorted(list(ans))
print(total - largest)
at = 0
for k in ans:
    at = at + 1
    if at == total - largest:
        print(k, end="\n")
        quit()
    print(k, end=" ")


n = int(input())
B = list(map(int, input().split()))
A = []
for i in range(100):
    A.append([])
for i in B:
    x = i
    c = 0
    while x % 2 == 0:
        x //= 2
        c += 1
    A[c].append(i)
mlen = 0
f = 1
for lst in A:
    mlen = max(mlen, len(lst))
ans = []
for lst in A:
    if len(lst) == mlen and f:
        f = 0
    else:
        for x in lst:
            ans.append(x)
print(len(ans))
print(' '.join(list(map(str, ans))))

n=int(input())
l=list(map(int,input().split()))
arr=[0]*65
ll=[0]*n
for i in range(n):
    cou=0
    a=l[i]
    while a%2==0:
        cou+=1
        a=a//2
    arr[cou]+=1
    ll[i]=cou
#print(arr)
m=arr.index(max(arr))
res=[]
rak=0
for i in range(n):
    if(ll[i]==m):
        rak+=1
    else:
        res.append(l[i])
print(n-rak)
if(n-rak):
    print(*res)

try:
    from string_source import string_source

    source = string_source(
        """2
2 6"""
    )
except ImportError:
    source = input

from collections import Counter


def two_factors(n):
    if n == 0:
        return 0

    f = 0
    while n % 2 == 0:
        f += 1
        n //= 2

    return f


def f(numbers):
    twos = list(map(two_factors, numbers))
    m = max(list(Counter(twos).items()), key=lambda x: x[1])[0]
    erased = [n for (n, t) in zip(numbers, twos) if t != m]
    return len(erased), erased


source()
n, erased = f(list(map(int, source().split(" "))))
print(n)
print(" ".join(map(str, erased)))


n = int(input())
u = list(map(int, input().split()))
a = []
for i in range(n):
    a.append(len(bin(u[i] & -u[i])[2:]))
#print(a)
x = [0] * 61
for i in range(len(a)):
    x[a[i]] += 1
#print(x)
mx = max(x)
p = -1
for i in range(61):
    if x[i] == mx:
        p = i
        break
#print(p)
q = []
for i in range(n):
    if a[i] != p:
        q.append(u[i])
print(len(q))
print(' '.join(map(str, q)))


#Bhargey Mehta (Junior)
#DA-IICT, Gandhinagar
import sys, math, queue
#sys.stdin = open('input.txt', 'r')
MOD = 10**9+7
sys.setrecursionlimit(1000000)

n = int(input())
a = list(map(int, input().split()))
x = {}
for i in range(n):
    p = 0
    t = a[i]
    while t%2 == 0:
        p += 1
        t = t>>1
    if p in x:
        x[p].append(a[i])
    else:
        x[p] = [a[i]]
keep = []
for k in x:
    if len(x[k]) > len(keep):
        keep = x[k]
print(n-len(keep))
keep = set(keep)
for ai in a:
    if ai not in keep:
        print(ai, end=' ')
print()

N = int(input())
*B, = map(int, input().split())
C = [0]*64
L = [[] for i in range(64)]
for b in B:
    l = (b & -b).bit_length()
    C[l] += 1
    L[l].append(b)
i = C.index(max(C))
R = [b for b in B if (b & -b).bit_length() != i]
print(len(R))
if R:
    print(*R)