The Gray code (see wikipedia for more details) is a well-known concept.
One of its important properties is that every two adjacent numbers have exactly one different digit in their binary representation.

In this problem, we will give you n non-negative integers in a sequence A[1..n] (0<=A[i]<2^64), such that every two adjacent integers have exactly one different digit in their binary representation, similar to the Gray code.

Your task is to check whether there exist 4 numbers A[i1], A[i2], A[i3], A[i4] (1 <= i1 < i2 < i3 < i4 <= n) out of the given n numbers such that A[i1] xor A[i2] xor A[i3] xor A[i4] = 0. Here xor is a bitwise operation which is same as ^ in C, C++, Java and xor in Pascal.

-----Input-----
First line contains one integer n (4<=n<=100000).
Second line contains n space seperated non-negative integers denoting the sequence A.

-----Output-----
Output “Yes” (quotes exclusive) if there exist four distinct indices i1, i2, i3, i4 such that A[i1] xor A[i2] xor A[i3] xor A[i4] = 0. Otherwise, output "No" (quotes exclusive) please.

-----Example-----
Input:

5
1 0 2 3 7

Output:

Yes

Difficulty: interview

Starter code:

Solutions:
dic = {}
#num = "1"
#def tonum(num):
#   res=0
#   for i in range(len(num)):
#       res = 2*res + int(num[i])
#   return res

#for i in range(64):
#   number = tonum(num)
#   dic[num] = []
#   num = num+"0"

n = int(input())
flag=0
if n >= 68:
 inp = input()
 print("Yes")
else:
 inp = [int(x) for x in input().split()]
 for i in range(len(inp)-1):
  for j in range(i+1,len(inp)):
   xor = inp[i]^inp[j]
   if xor in list(dic.keys()):
    for pair in dic[xor]:
     (x,y) = pair
     if x != i and y!=j and x!=j and y!=i:
      flag = 1
      break

    dic[xor].append((i,j))
   else:
    dic[xor] = []
    dic[xor].append((i,j))
   if flag is 1:
    break
  if flag is 1:
   break

 if flag is 1:
  print("Yes")
 else:
  print("No")
 
 


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

d={}
for i in range(1,n):
 x1,x2=hit[i],hit[i-1]
 try: d[x1^x2]+=[i]
 except: d[x1^x2]=[i]

done=False
for i in d:
 x=d[i]
 if len(x)>2: done=True; break
 elif len(x)==2:
  x=sorted(x)
  if x[0]!=x[1]-1: done=True; break

if done: print('Yes')
else:
 v={}
 for i in hit:
  try: v[i]+=1
  except: v[i]=1
 x={}
 h=list(v.values())
 for i in h:
  try: x[i]+=1
  except: x[i]=1
 if ( 2 in x and x[2]==2 ) or ( 4 in x and x[4]==1 ): print('Yes')
 else: print('No')


#!/usr/bin/python
from math import log
flips = {}

def get_flip(a,b):
 temp = a^b
 ans = log(temp)/log(2)
 return int(ans)

def main():
 n = input()
 nums = input()
 nums = [int(i) for i in nums.split()]
 l = len(nums)
 for i in range(1,l):
  f = get_flip(nums[i-1], nums[i])
  if f in flips:
   if flips[f] != i-1:
    print('Yes')
    return
  else:
   flips[f] = i

 # now check in case of same elements
 rec = {}
 for i in nums:
  if i in rec:
   rec[i] += 1
  else:
   rec[i] = 1
 

 r = 0
 for i in rec:
  if rec[i] > 1:
   r += int(rec[i]/2)
  if r >= 2:
   print('Yes')
   return
 print('No')
 return


def __starting_point():
 main()


__starting_point()

#!/usr/bin/python
from math import log
flips = {}

def get_flip(a,b):
 temp = a^b
 ans = log(temp)/log(2)
 return int(ans)

def main():
 n = input()
 nums = input()
 nums = [int(i) for i in nums.split()]
 l = len(nums)
 for i in range(1,l):
  f = get_flip(nums[i-1], nums[i])
  if f in flips:
   if flips[f] != i-1:
    print('Yes')
    return
  else:
   flips[f] = i

 # now check in case of same elements
 rec = {}
 for i in nums:
  if i in rec:
   rec[i] += 1
  else:
   rec[i] = 1
 

 r = 0
 for i in rec:
  if rec[i] > 1:
   r += int(rec[i]/2)
  if r == 2:
   print('Yes')
   return
 print('No')
 return


def __starting_point():
 main()


__starting_point()

n = int(input())
s = input()
s = s.split()
d = {}
flag = "No"

two,four = 0,0
for i in s:
 if i in d:
  d[i] += 1;
  if d[i] == 2:
   two += 1
  elif d[i] == 4:
   four += 1
 else:
  d[i] = 1;
d = {}
if two>1 or four>0:
 flag = "Yes"
else:
 
 for i in range(n-1):
  ex = int(s[i]) ^ int(s[i+1])
  if ex in d:
   d[ex].append(i)
   if d[ex][-1] - d[ex][0] > 1:
    flag = "Yes"
    break;  
  else:
   d[ex] = [i]
print(flag)


n = int(input())
s = input()
s = s.split()
d = {}
flag = "No"

two,four = 0,0
for i in s:
 if i in d:
  d[i] += 1;
  if d[i] == 2:
   two += 1
  elif d[i] == 4:
   four += 1
 else:
  d[i] = 1;

if two>1 or four>0:
 flag = "Yes"
else:
 for i in range(n-1):
  ex = int(s[i]) ^ int(s[i+1])
  if ex in d:
   d[ex].append(i)
   if d[ex][-1] - d[ex][0] > 1:
    flag = "Yes"
    break;  
  else:
   d[ex] = [i]
print(flag)


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

d={}
for i in range(1,n):
 x1,x2=hit[i],hit[i-1]
 try: d[x1^x2]+=[i]
 except: d[x1^x2]=[i]

done=False
for i in d:
 x=d[i]
 if len(x)>2: done=True; break
 elif len(x)==2:
  x=sorted(x)
  if x[0]!=x[1]-1: done=True; break

if done: print('Yes')
else:
 v={}
 for i in hit:
  try: v[i]+=1
  except: v[i]=1
 x={}
 h=list(v.values())
 for i in h:
  try: x[i]+=1
  except: x[i]=1
 if ( 2 in x and x[2]==2 ) or ( 4 in x and x[4]==1 ): print('Yes')
 else: print('No')


def digit(x):
 ans = None
 for i in range(64):
  if x&(1<<i): 
   return i
  
#data = open("P7.txt")
n = int(input())
#n = int(data.readline())
if n<4:
 print("No")
 
else:
 count = [0]*65
 nums = {}
 vals = list(map(int,input().split()))
 #vals = map(long,data.readline().split())
 nums[vals[0]] = 1
 prebit = 999999999
 
 for i in range(1,n):
  bit = digit(vals[i]^vals[i-1])
  if bit!=prebit:
   count[bit] += 1
   prebit = bit
  try:
   nums[vals[i]] += 1
  except:
   nums[vals[i]] = 1
  
 m1 = max(count)
 m2 = max(nums.values())
 if m1>=2 or m2>=4: print("Yes")
 else: 
  num_doubles = 0
  for val in list(nums.values()):
   if val >= 2:
    num_doubles += 1
  if num_doubles >= 2:
   print("Yes")
  else:
   print("No")

import sys

n = int(input())
a = [0]*n
if (n > 300):
 print('Yes')
 return
s = input().split()
for i in range(n):
 a[i] = int(s[i]) 
a.sort()
for i in range(n-3):
 for j in range(i+1, n-2):
  for k in range(j+1, n-1):
   x = (a[i]^a[j])^a[k]
   l = k + 1
   r = n - 1
   while r - l > 1:
    c = ( r + l ) / 2
    if a[c] > x:
     r=c
    else:
     l=c
   if ((l > k and a[l] == x) or (a[r]==x)):
    print('Yes')
    return
print('No')