There is an array with n elements a_1, a_2, ..., a_{n} and the number x.

In one operation you can select some i (1 ≤ i ≤ n) and replace element a_{i} with a_{i} & x, where & denotes the bitwise and operation.

You want the array to have at least two equal elements after applying some operations (possibly, none). In other words, there should be at least two distinct indices i ≠ j such that a_{i} = a_{j}. Determine whether it is possible to achieve and, if possible, the minimal number of operations to apply.


-----Input-----

The first line contains integers n and x (2 ≤ n ≤ 100 000, 1 ≤ x ≤ 100 000), number of elements in the array and the number to and with.

The second line contains n integers a_{i} (1 ≤ a_{i} ≤ 100 000), the elements of the array.


-----Output-----

Print a single integer denoting the minimal number of operations to do, or -1, if it is impossible.


-----Examples-----
Input
4 3
1 2 3 7

Output
1

Input
2 228
1 1

Output
0

Input
3 7
1 2 3

Output
-1



-----Note-----

In the first example one can apply the operation to the last element of the array. That replaces 7 with 3, so we achieve the goal in one move.

In the second example the array already has two equal elements.

In the third example applying the operation won't change the array at all, so it is impossible to make some pair of elements equal.

Difficulty: interview

Starter code:

Solutions:
n, x = list(map(int, input().split()))
a = list(map(int, input().split()))
b = [0] * 1000000
ans = 0
go = False

for i in a:
    b[i] += 1
    if b[i] > 1:
        go = True

if go:
    print(ans)
else:
    for i in a:
        b[i] -= 1
        if b[i & x] + 1 > 1:
            go = True
            ans = 1
            break
        
        b[i] += 1
    
    if go:
        print(ans)
    else:
        c = [i & x for i in a]
        b = [0] * 1000000
        for i in c:
            b[i] += 1
            if (b[i] > 1):
                ans = 2
                go = True
                break
        if go:
            print(ans)
        else:
            print(-1)


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

data = list(map(int,input().split()))

s = set(data)

if len(s) < len(data):
    print(0)
    return


answer = -1

ss = set()
prevs = set()

for el in data:
    curr = el & x
    
    if curr in prevs or el in ss:
        answer = 1

    prevs.add(el)

    if curr in ss and answer != 1:
        answer = 2
        
    ss.add(curr)

print(answer)

    


import sys
import os

def solve(a, x):
    occ = dict()
    for k in a:
        if k in occ:
            return 0
        else:
            occ[k] = True

    two = False
    occx = dict()
    for k in a:
        if k & x == k:
            continue
        elif k & x in occ:
            return 1
        elif k & x in occx:
            two = True
        else:
            occx[k & x] = True

    return 2 if two else -1

def main():
    n, x = map(int, input().split())

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

    print(solve(a, x))

def __starting_point():
    main()
__starting_point()

n, x = [int(v) for v in input().split()]
a = [int(v) for v in input().split()]

sa = set(a)

if len(sa) < n:
    print(0)
else:
    la = [v & x for v in a if v & x != v]
    if set(la) & sa:
        print(1)
    else:
        if len(set(la)) < len(la):
            print(2)
        else:
            print(-1)


n, x = list(map(int, input().split()))
a = sorted(map(int, input().split()))
s = set(a)
b = sorted([u & x for u in a])
t = set(b)

if len(s) < len(a):
    print(0)
elif any([u != (u & x) and (u & x) in s for u in a]):
    print(1)
elif len(t) < len(b):
    print(2)
else:
    print(-1)


n, x = list(map(int,input().split()))
a = set(int(i) for i in input().split())
if len(a)!=n:
    ans = 0
else:
    shift = set()
    ans = -1
    for i in a:
        shift.add(i & x)
        if i&x != i and i&x in a:
            ans = 1
    if len(shift)!=n and ans == -1:
        ans = 2
print(ans)



n,m=list(map(int,input().split()))
l=list(map(int,input().split()))
d={}
ansz=0
for i in l:
  if(i in d):
    ansz=1
  else:
    d[i]=1
lz=[]
ans1=0
for i in l:
  lz.append(i&m)
  if(i&m in d and i&m!=i):
    ans1=1

ans2=0
dz={}
for i in lz:
  if(i in dz):
    ans2=1
  else:
    dz[i]=1

if(ansz):
  print(0)
elif(ans1):
  print(1)
elif(ans2):
  print(2)
else:
  print(-1)



n, x = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
f = [False] * (max(a) + 1)
for i in a:
    if f[i]:
        print(0)
        quit()
    f[i] = True

wk1 = []
for i in range(n):
    wk1.append(a[i] & x)

f = [False] * (max(a) + 1)
position = [-1] * (max(a) + 1)
for i in range(n):
    f[a[i]] = True
    position[a[i]] = i

for i in range(n):
    if f[wk1[i]] and (position[wk1[i]] != i):
        print(1)
        quit()

f = [False] * (max(wk1) + 1)
for i in wk1:
    if f[i]:
        print(2)
        quit()
    f[i] = True

print(-1)




# from math import ceil
#from sys import stdout

t = 1#int(input())
for test in range(1,t+1):
    n,x = list(map(int, input().split()))
    b = list(map(int, input().split()))
    a = set(b)
    ans = -1
    if len(a)-len(b)<0:
        ans = 0
    else:
        D = {}
        for i in b:
            if i in D:
                D[i]+=1
            else:
                D[i] = 1
        for i in b:
            if (i&x) in D:
                if i==(i&x):
                    if D[i]>1:
                        ans = 1
                        break
                else:
                    ans = 1
                    break
        if ans==-1:
            tmp = []
            for i in b:
                tmp.append(i&x)
            if len(tmp)>len(set(tmp)):
                ans = 2
    print(ans)



    


n, x = map(int, input().split())
a = list(map(int, input().split()))
ans = 100
o = set()
c = set()

for i in range(n):
    if a[i] in o:
        ans = min(ans, 0)
    elif a[i] in c:
        ans = min(ans, 1)
    elif a[i] & x in o:
        ans = min(ans, 1)
    elif a[i] & x in c:
        ans = min(ans, 2)
    o.add(a[i])
    c.add(a[i]&x)
print(-1 if ans == 100 else ans)

can11 = set()
can12 = set()
can2 = False
n, x = list(map(int, input().split()))
a = list(map(int, input().split()))
for ai in a:
	if ai in can11:
		print('0')
		break
	can11.add(ai)
	ai2 = ai & x
	if ai2 == ai:
		continue
	if ai2 in can12:
		can2 = True
	else:
		can12.add(ai2)
else:
	can11.intersection_update(can12)
	if can11:
		print(1)
	elif can2:
		print(2)
	else:
		print('-1')


from collections import *

n, m = map(int, input().split())

a = [int(i) for i in input().split()]

st = set(a)
if len(st) < n:
    print(0);return

mp = defaultdict(int)
for i in a:
    mp[i] += 1

for i in a:
    mp[i] -= 1
    if (mp[i & m] > 0):
        print(1);return
    mp[i] += 1

st.clear()

for i in a:
    t = m
    if (i & t) in st:
        print(2);return
    st.add(i & t)

print(-1)


def getUsefulWeight(coef, uw):
    if coef == 1:
        print(-1)
        return
    uw += (uw/(coef-1))
    return uw

#n = int(input().strip())
#x = int(input().strip())
n,x = list(map(int, input().strip().split(" ")))

a = list(map(int, input().strip().split(" ")))
d = {}
ret = 3
for y in  a:
    val = y&x
    if y in d:
        newc = d[y]
        if ret > newc:
            ret = newc
    if val in d:
        newc = d[val]+1
        if ret > newc:
            ret = newc
    d[y] = 0
    if val not in d:
        d[val] = 1

if ret == 3:
    print("-1")
else:
    print(ret)



n,x=map(int,input().split())
a=list(map(int,input().split()))
b=[0]*(100001);c=[0]*100001
for i in a:
    b[i]+=1
    if b[i]>=2:
        print(0);return
for i in a:
    b[i]-=1
    if b[i&x]>=1:
        print(1);return
    b[i]+=1
for i in a:
    c[i&x]+=1
    if c[i&x]>=2:
        print(2);return
print(-1)

n,x = list(map(int,input().split()))
l = list(map(int,input().split()))
a =[0]*(10**5+1)
b=[0]*(10**5+1)
count =0
flag=0
for i in range(n):
    if a[l[i]-1] == 0:
        a[l[i]-1] = 1
    else:
        count = 0
        flag=1
if flag == 0:
    for i in range(n):
        if a[(l[i]&x)-1] == 1 and l[i]&x != l[i]:
            count =1
            break
        else:
            if b[(l[i]&x)-1] == 1 :
                count =2
        b[(l[i]&x)-1] =1
if flag == 0 and count == 0:
    print('-1')
else:
    print(count)


n, x = list(map(int, input().split()))
a = list(map(int, input().split()))
d = {}
t = {}
ok = False

for i in a:
    try:
        d[i] += 1
    except KeyError:
        d[i] = 1

for i in a:
    if d[i] > 1:
        print(0)
        return
    tmp = x & i

    if tmp != i:
        try:
            t[tmp] += 1
            # if t[tmp] == 2:
            #     ok = True
            #     t[tmp] -= 1
        except KeyError:
            t[tmp] = 1

# print(d)
# print(t)

for i in t:
    try:
        tmp = d[i]
    except KeyError:
        tmp = 0

    if t[i] > 1:
        ok = True
    if t[i] >= 1 and tmp == 1:
        print(1)
        return

if ok:
    print(2)
else:
    print(-1)



[n,x] = [int(i) for i in input().split()]
nums = [int(i) for i in input().split()]


def foo():
    nonlocal x,n,nums
    a_plain = set()
    
    for i in range(n):
        if nums[i] not in a_plain:
            a_plain.add(nums[i])
        else:
            print(0)
            return

    for i in range(n):
        if (nums[i] & x) in a_plain and (nums[i] & x != nums[i]):
            print(1)
            return
    
    a_and = {}
    for i in range(n):
        temp = nums[i] & x
        if temp not in a_and:
            a_and[temp] = 1
        else:
            a_and[temp] += 1
    
    for k in a_and:
        if a_and[k] > 1:
            print(2)
            return
    print(-1)
        

foo()

from collections import Counter

n, x = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

if Counter(A).most_common()[0][1] >= 2:
    print(0)
    return

setA = set(A)
B = []

for a in A:
    B.append(a & x)

ans = -1

for b, c in Counter(B).most_common():
    if c >= 2:
        if b in setA:
            ans = 1
            break
        else:
            ans = 2
    else:
        break

print(ans)

from sys import stdin,exit
def listInput():
	return list(map(int,stdin.readline().rstrip().split()))

n,x= listInput()
li = listInput()
dic1 = {}
#print('x is ',x)
for i in li:
	if i in dic1: dic1[i]+=1
	else : dic1[i]=1
dic2 = {}
for i in li:
	#print('for ',i,' &x is ',i&x)
	if i&x in dic2: dic2[i&x]+=1
	else : dic2[i&x]=1
ans = n+1
#rint(dic1)
#print(dic2)
for i in li:
	if dic1[i]>=2:
		ans=min(ans,0)	
	elif i!=(i&x) and (i&x) in dic1:
		ans = min(ans,1)
	elif (i&x) in dic1 and dic1[i&x]>=2:
		ans = min(ans,1)
	elif i!=(i&x) and i in dic2:
		ans = min(ans,1)
	elif (i&x) in dic2 and dic2[i&x]>=2:
		ans = min(ans,2)

if ans == (n+1):
	print(-1)
else :
	print(ans)


import sys

n,x=list(map(int,input().split()))
A=list(map(int,input().split()))

A.sort()
check=0
for i in range(1,n):
    if A[i]==A[i-1]:
        check=1
        break

if check==1:
    print(0)
    return

B=[A[i] for i in range(n)]

for i in range(n):
    A[i]=A[i] & x

AX=[(A[i],i) for i in range(n)]

AX.sort()

check=0
i=0
j=0
while i<n:
    if AX[i][0]==B[j]:
        if AX[i][1] != j:
            check=1
            break
        else:
            i+=1
    elif AX[i][0]<B[j]:
            i+=1
    elif AX[i][0]>B[j]:
        j+=1

if check==1:
    print(1)
    return
        

check=0
for i in range(1,n):
    if AX[i][0]==AX[i-1][0]:
        check=1
        break

if check==1:
    print(2)
    return

print(-1)



def main2():
    n, x = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]

    a.sort()

    count = 9999

    for i in range(len(a) - 1):
        f, s = a[i], a[i + 1]
        if f == s:
            print(0)
            return
        if f & x == s & x:
            if count > 2:
                count = 2
        if f == s & x:
            if count > 1:
                count = 1

    if count == 9999:
        print(-1)
    else:
        print(count)


def main():
    n, x = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]

    anded = set()

    count = 9999

    a.sort()
    init = {}

    for i, e in enumerate(a):
        if e not in init:
            init[e] = set()

        init[e].add(i)

    for i in range(len(a)):
        f = a[i]

        if i < len(a) - 1:
            s = a[i + 1]
            if f == s:
                print(0)
                return

        fx = f & x
        init[f].remove(i)
        if fx in init and init[fx]:
            if count > 1:
                count = 1

        init[f].add(i)

        if fx in anded:
            if count > 2:
                count = 2

        anded.add(fx)

    if count == 9999:
        print(-1)
    else:
        print(count)


def __starting_point():
    main()

__starting_point()

#!/usr/bin/env python3
from sys import stdin, stdout

def rint():
    return map(int, stdin.readline().split())
#lines = stdin.readlines()


n, x = rint()

a = list(rint())

a_dict = dict()
for i in range(n):
    if a[i] not in a_dict:
        a_dict[a[i]] = 1
    else:
        a_dict[a[i]] += 1

if n > len(a_dict):
    print("0")
    return

for i in range(n):
    if a[i]&x in a_dict:
        if a[i]&x == a[i]:
            if a_dict[a[i]&x] >= 2:
                print("1")
                return
        else:
            print("1")
            return

ax = [a[i]&x for i in range(n)]

ax_set = set(ax)

if n > len(ax_set):
    print("2")
else:
    print("-1")

from collections import Counter

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

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

bs = set(b.keys())


if b.most_common(1)[0][1]>1:
    print(0)
    return

k = Counter([a&x for a in list(b.keys()) if a&x != a])
ks = set(k.keys())
if len(ks.intersection(bs))>0:
    print(1)
    return

if len(k) >0 and k.most_common(1)[0][1]>1:
    print(2)
    return
print(-1)









n, x  = map(int, input().split())
a = list(map(int, input().split()))
dp = [10**9 for i in range(max(a)+1)]
for i in range(n):
    if(dp[a[i]] == 0):
        print(0)
        return
    dp[a[i]] = 0
j= len(dp)-1

ans = 10**9
while j >=0:
    if dp[j] != 10**9:
        if(dp[j&x] != 10**9 and j !=j&x):
            ans = min(ans, dp[j&x] + dp[j]+1)
        dp[j&x] = min(dp[j&x], dp[j]+1)
    j-=1
if(ans==10**9):
    print(-1)
    return
print(ans)

from sys import stdin, stdout 

# string input
n, x= stdin.readline().split()
n, x = int(n), int(x)

arr = [int(y) for y in stdin.readline().split()]

arr.sort()

flag = 0
for i in range(len(arr)-1):
	if(arr[i] == arr[i+1]):
		print(0)
		flag = 1
		break

if flag == 0:
	arr1 = [(arr[i] & x) for i in range(len(arr))]
	arr2 = [(arr1[i], arr[i]) for i in range(len(arr))]
	arr2 = sorted(arr2, key=lambda x: x[0])
	#print(arr2)
	currentAns = -1
	for i in range(len(arr2)-1):
		if(arr2[i][0] == arr2[i+1][0]):
			if (arr2[i][0] == arr2[i][1] or arr2[i+1][0] == arr2[i+1][1]):
				currentAns = 1
				flag = 1
				break
			else:
				currentAns = 2
	print(currentAns)

# print to stdout
#stdout.write(str(summation))