A sophomore Computer Science student is frustrated with boring college lectures. Professor X agreed to give him some questions; if the student answers all questions correctly, then minimum attendance criteria will not apply to him.
Professor X chooses a sequence $A_1, A_2, \ldots, A_N$ and asks $Q$ queries. In each query, the student is given an integer $P$; he has to construct a sequence $B_1, B_2, \ldots, B_N$, where $P \oplus A_i = B_i$ for each valid $i$ ($\oplus$ denotes bitwise XOR), and then he has to find the number of elements of this sequence which have an even number of $1$-s in the binary representation and the number of elements with an odd number of $1$-s in the binary representation. Help him answer the queries.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains two space-separated integers $N$ and $Q$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.
- $Q$ lines follow. Each of these lines contains a single integer $P$ describing a query.

-----Output-----
For each query, print a single line containing two space-separated integers ― the number of elements with an even number of $1$-s and the number of elements with an odd number of $1$-s in the binary representation.

-----Constraints-----
- $1 \le T \le 100$
- $1 \le N, Q \le 10^5$
- $ T \cdot (N+Q) \leq 4 \cdot 10^6 $
- $1 \le A_i \le 10^8$ for each valid $i$
- $1 \le P \le 10^5$
The input/output is quite large, please use fast reading and writing methods.

-----Subtasks-----
Subtask #1 (30 points): $N, Q \le 1,000$
Subtask #2 (70 points): original constraints

-----Example Input-----
1
6 1
4 2 15 9 8 8
3

-----Example Output-----
2 4

-----Explanation-----
Example case 1: The elements of the sequence $B$ are $P \oplus 4 = 7$, $P \oplus 2 = 1$, $P \oplus 15 = 12$, $P \oplus 9 = 10$, $P \oplus 8 = 11$ and $P \oplus 8 = 11$. The elements which have an even number of $1$-s in the binary representation are $12$ and $10$, while the elements with an odd number of $1$-s are $7$, $1$, $11$ and $11$.

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
from sys import stdin, stdout

for _ in range(int(stdin.readline())):
 n, q = list(map(int, stdin.readline().split()))
 arr = list(map(int, stdin.readline().split()))[:n]
 od = ev = 0
 for i in arr:
  if bin(i).count('1')%2==0:
   ev += 1
  else:
   od += 1
 for _ in range(q):
  p = int(stdin.readline())
  if bin(p).count('1')%2==0:
   stdout.write(str(ev) + " " + str(od) + "\n")
  else:
   stdout.write(str(od) + " " + str(ev) + "\n")



for _ in range(int(input())):
 n,k = list(map(int,input().split()))
 a = list(map(int,input().split()))
 even,odd = 0,0
 for i in range(n):
  count_of_q = bin(a[i]).count('1')
  if count_of_q%2==0:
   even+=1
  else:
   odd+=1
 for i in range(k):
  q = int(input())
  count_of_i = bin(q).count('1')
  if count_of_i%2==0:
   print(even,odd)
  else:
   print(odd,even)


# cook your dish here
from sys import stdin, stdout

##Taken from geeksforgeeks
BitsSetTable256 = [0] * 256

def initialize(): 
 BitsSetTable256[0] = 0
 for i in range(256): 
  BitsSetTable256[i] = (i & 1) + BitsSetTable256[i // 2] 

def countSetBits(n): 
 return (BitsSetTable256[n & 0xff] +
   BitsSetTable256[(n >> 8) & 0xff] +
   BitsSetTable256[(n >> 16) & 0xff] +
   BitsSetTable256[n >> 24]) 

initialize()

for _ in range(int(stdin.readline())):
 N , Q = list(map(int, stdin.readline().split(' ')))
 inpList = list(map(int, stdin.readline().split(' ')))
 queryList = []
 resList = []
 even = odd = 0
 for i in inpList:
  temp = 1^i
  setBits = countSetBits(temp)
  if setBits %2 == 0:
   even += 1
  else:
   odd += 1
 for i in range(Q):
  q = int(stdin.readline())
  setBits = countSetBits(q)
  if setBits%2 != 0:
   stdout.write("{} {}\n".format(even,odd))
  else:
   stdout.write("{} {}\n".format(odd,even))
   
 #stdout.write("{} {} {} {} ".format(N,Q,inpList,*queryList))
 # cook your dish here


# cook your dish here
from sys import stdin, stdout
t=int(input())
for i in range(t):
 n,q=map(int,stdin.readline().split())
 a=list(map(int,stdin.readline().split()))
 even,odd=0,0
 for j in range(n):
  count=(bin(a[j]).count("1"))
  if count%2==0: 
   even+=1
  else:   
   odd+=1

 for j in range(q):
  m=int(stdin.readline())
  temp=bin(m).count("1")
  temp1,temp2=even,odd
  if temp%2==0:
   temp1,temp2=even,odd
  else: 
   temp1,temp2=odd,even
  stdout.write(str(temp1)+" "+str(temp2)) 
  stdout.write("\n")

# cook your dish here
t=int(input())
for i in range(t):
 n,q=list(map(int,input().split()))
 a=list(map(int, input().split()))
 even,odd=0,0
 for j in range(n):
  count=(bin(a[j]).count("1"))
  if count%2==0: 
   even = even + 1
  else:   
   odd = odd + 1

 for j in range(q):
  m=int(input())
  g=bin(m).count("1")
  a,b=even,odd
  if g%2==0:
   a,b=even,odd
  else: 
   a,b=odd,even
  print(a,b)


t=int(input())
for i in range(t):
 n,q=list(map(int,input().split()))
 a=list(map(int,input().split()))
 even,odd=0,0
 for j in range(n):
  count=(bin(a[j]).count("1"))
  if count%2==0: 
   even+=1
  else:   
   odd+=1

 for j in range(q):
  m=int(input())
  temp=bin(m).count("1")
  temp1,temp2=even,odd
  if temp%2==0:
   temp1,temp2=even,odd
  else: 
   temp1,temp2=odd,even
  print(temp1,temp2)


for _ in range(int(input())):
 n,q = list(map(int,input().split()))
 a = list(map(int,input().split()))
 even,odd=0,0
 for j in range(n):
  count=(bin(a[j]).count("1"))
  if count%2==0: 
   even+=1
  else:   
   odd+=1

 for j in range(q):
  m=int(input())
  temp=bin(m).count("1")
  temp1,temp2=even,odd
  if temp%2==0:
   temp1,temp2=even,odd
  else: 
   temp1,temp2=odd,even
  print(temp1,temp2)


for _ in range(int(input())):
 n,q = list(map(int,input().split()))
 a = list(map(int,input().split()))
 even = 0
 odd = 0
 for i in range(n):
  c = bin(a[i]).count("1")
  if c%2 == 0:
   even += 1
  else:
   odd +=1
 for i in range(q):
  p = int(input())
  c = bin(p).count("1")
  e,o = even,odd
  if c%2 == 0:
   e,o =even,odd
  else:
   e,o = odd,even
  print(e,o)
  


# cook your dish here
for _ in range(int(input())):
 n,q=map(int,input().split())
 a=list(map(int,input().split()))
 even,odd=0,0
 for i in range(n):
  c=bin(a[i]).count('1')
  if c%2==0:
   even+=1 
  else:
   odd+=1 
 for j in range(q):
  m=int(input())
  t=bin(m).count('1')
  temp1,temp2=even,odd
  if t%2==0:
   temp1,temp2=even,odd
  else:
   temp1,temp2=odd,even
  print(str(temp1)+" "+str(temp2))

# cook your dish here
from sys import stdin, stdout
t=int(input())
for i in range(t):
 n,q=list(map(int,stdin.readline().split()))
 a=list(map(int,stdin.readline().split()))
 even,odd=0,0
 for j in range(n):
  count=(bin(a[j]).count("1"))
  if count%2==0: 
   even+=1
  else:   
   odd+=1

 for j in range(q):
  m=int(stdin.readline())
  temp=bin(m).count("1")
  temp1,temp2=even,odd
  if temp%2==0:
   temp1,temp2=even,odd
  else: 
   temp1,temp2=odd,even
  stdout.write(str(temp1)+" "+str(temp2)) 
  stdout.write("\n")


Bit= [0] * 256
def initialize(): 
 Bit[0] = 0
 for i in range(256): 
  Bit[i] = (i & 1) + Bit[i // 2] 
def countsetbits(n): 
 return (Bit[n & 0xff] +
   Bit[(n >> 8) & 0xff] +
   Bit[(n >> 16) & 0xff] +
   Bit[n >> 24]) 
initialize()
t=int(input())
for _ in range(t):
 n,q=map(int, input().split())
 a=list(map(int, input().split()))
 e=0
 o=0
 for i in a:
  k=countsetbits(i)
  if (k&1)==0:
   e+=1
  else:
   o+=1
 for j in range(q):
  c=0
  n1=int(input())
  c=countsetbits(n1)
  if c%2==0:
   print(e,o)
  else:
   print(o,e)

Bit= [0] * 256
def initialize(): 
 Bit[0] = 0
 for i in range(256): 
  Bit[i] = (i & 1) + Bit[i // 2] 
def countsetbits(n): 
 return (Bit[n & 0xff] +
   Bit[(n >> 8) & 0xff] +
   Bit[(n >> 16) & 0xff] +
   Bit[n >> 24]) 
initialize()
t=int(input())
for _ in range(t):
 n,q=map(int, input().split())
 a=list(map(int, input().split()))
 e=0
 o=0
 for i in a:
  k=countsetbits(i)
  if (k&1)==0:
   e+=1
  else:
   o+=1
 for j in range(q):
  c=0
  n1=int(input())
  c=countsetbits(n1)
  if c%2==0:
   print(e,o)
  else:
   print(o,e)

from sys import stdin,stdout
def main():
 t=int(stdin.readline())
 for i in range(t):
  list2=[]
  n,q=map(int,stdin.readline().split()) 
  a=list(map(int,stdin.readline().split()))
  for i in range(len(a)):                     
   list2.append((bin(a[i])).count("1"))
  o=0
  e=0
  for i in range(len(list2)):
    if((list2[i]%2)==0):
     e+=1
    else:
     o+=1
  for i in range(q):                          
   b=0
   b=int(stdin.readline())
   e1=0
   e1=bin(b).count("1")
   if(e1%2==0):
    print(e,end=" ")
    print(o)
   else:
    print(o,end=" ")
    print(e)
def __starting_point():
 main()
#a=5
#str1=""
#str1+=bin(a)
#print(str1[2:])

__starting_point()

from sys import stdin,stdout
def main():
 t=int(stdin.readline())
 for i in range(t):
  list2=[]
  n,q=map(int,stdin.readline().split()) 
  a=list(map(int,stdin.readline().split()))
  for i in range(len(a)):                     
   list2.append((bin(a[i])).count("1"))
  for i in range(q):                          
   b=0
   b=int(stdin.readline())
   e=0
   o=0
   for i in range(len(list2)):
    if((list2[i]%2)==0):
     e+=1
    else:
     o+=1
   e1=0
   e1=bin(b).count("1")
   if(e1%2==0):
    print(e,end=" ")
    print(o)
   else:
    print(o,end=" ")
    print(e)
def __starting_point():
 main()
#a=5
#str1=""
#str1+=bin(a)
#print(str1[2:])

__starting_point()


import sys

T = int(sys.stdin.readline())
from collections import defaultdict

ans = []
for _ in range(T):
 n ,q = map(int ,sys.stdin.readline().split())
 x = list(map( int ,sys.stdin.readline().split()))

 
 dic = defaultdict(int)
 
 for ele in x:
  if(bin(ele).count('1') %2 == 0):
   dic['even'] += 1
  else:
   dic['odd'] += 1
  
 for o in range(q):
  l = int(sys.stdin.readline())
  
  
  if(bin(l).count('1') % 2 != 0):
   print(dic['odd'],dic['even'])
  else:
   print(dic['even'],dic['odd'])

# # cook your dish here
# import sys
# from sys import stdin, stdout
# for _ in range(int(stdin.readline())):
#     N, Q = map(int, stdin.readline().rstrip().split())
#     Num = list(map(int, stdin.readline().split()))
#     for _ in range(Q):
#         P = int(stdin.readline())
#         x = bin(P).count('1')
#         even = 0
#         for i in range(len(Num)):
#             y = bin(Num[i]).count('1')
#             if x % 2 == 0:
#                 if y % 2 == 0:
#                     even += 1
#             else:
#                 if y % 2 != 0:
#                     even += 1
#         stdout.write(str(even) + " " + str(N-even))

import sys

T = int(sys.stdin.readline())
from collections import defaultdict

ans = []
for _ in range(T):
 n ,q = list(map(int ,sys.stdin.readline().split()))
 x = list(map( int ,sys.stdin.readline().split()))

 
 dic = defaultdict(int)
 
 for ele in x:
  if(bin(ele).count('1') %2 == 0):
   dic['even'] += 1
  else:
   dic['odd'] += 1
  
 for o in range(q):
  l = int(sys.stdin.readline())
  
  
  if(bin(l).count('1') % 2 != 0):
   print(dic['odd'],dic['even'])
  else:
   print(dic['even'],dic['odd'])


t=int(input())
for i in range(t):
 num_to_bits =[0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4]
 def countSetBitsRec(num):
  nibble = 0
  if(0 == num):
   return num_to_bits[0] 
  nibble = num & 0xf 
  return num_to_bits[nibble] + countSetBitsRec(num >> 4)
 n,q=input().split()
 n=int(n)
 q=int(q)
 A=[]
 A=list(map(int,input().split()))
 od=0
 ev=0
 for j in range(n):
  num=A[j]
  co=countSetBitsRec(num)
  if(co%2==0):
   ev+=1
  else:
   od+=1
 for j in range(q):
  p=int(input())
  co=countSetBitsRec(p)
  if(co%2==0):
   print(ev,end=' ')
   print(od)
  else:
   print(od,end=' ')
   print(ev)