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: MEDIUM_HARD
Tags: Mathematics

Starter code:

Solutions:
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'])


t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	(op, zp) = (0, 0)
	for i in a:
		curr = bin(i).count('1')
		if curr & 1:
			op += 1
		else:
			zp += 1
	query = [int(input()) for i in range(q)]
	for b in query:
		p = bin(b).count('1')
		if p & 1:
			print(op, zp)
		else:
			print(zp, op)


import sys
from os import path
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
t = int(sys.stdin.readline())
for _ in range(t):
	[N, Q] = list(map(int, sys.stdin.readline().split()))
	arr = list(map(int, sys.stdin.readline().split()))
	(even, odd) = (0, 0)
	for i in range(N):
		temp = bin(arr[i]).count('1')
		if temp % 2 == 0:
			even += 1
		else:
			odd += 1
	for j in range(Q):
		p = int(sys.stdin.readline())
		p_ones = bin(p).count('1')
		if p_ones % 2 == 0:
			print(even, odd)
		else:
			print(odd, even)


from sys import stdin, stdout
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 & 255] + BitsSetTable256[n >> 8 & 255] + BitsSetTable256[n >> 16 & 255] + 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))


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')


import sys

def input():
	return sys.stdin.readline()
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	arr = [int(i) for i in input().strip().split(' ')]
	odd = 0
	even = 0
	for i in arr:
		if bin(i)[2:].count('1') % 2 == 0:
			even += 1
		else:
			odd += 1
	for _ in range(q):
		p = bin(int(input()))[2:].count('1')
		if p % 2 == 0:
			print(even, odd)
		else:
			print(odd, even)


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)
main()


from sys import stdin
t = int(stdin.readline())
while t:
	(n, q) = [int(x) for x in stdin.readline().split()]
	a = [f'{int(x):b}' for x in stdin.readline().split()]
	(od, ev) = (0, 0)
	for x in a:
		cnt = x.count('1')
		if cnt % 2:
			od += 1
		else:
			ev += 1
	while q:
		query = int(stdin.readline())
		cons = f'{query:b}'
		odd_even = cons.count('1')
		if odd_even % 2:
			print(od, ev)
		else:
			print(ev, od)
		q -= 1
	t -= 1


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)


from sys import stdin
for tc in range(int(stdin.readline())):
	(N, Q) = map(int, stdin.readline().split())
	n_list = list(map(int, stdin.readline().split()))
	(even, odd) = (0, 0)
	for i in n_list:
		if bin(i)[2:].count('1') % 2 == 0:
			even += 1
		else:
			odd += 1
	for q in range(Q):
		P = int(stdin.readline())
		if bin(P).count('1') % 2 == 0:
			print(even, odd)
		else:
			print(odd, even)


import sys
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 & 255] + BitsSetTable256[n >> 8 & 255] + BitsSetTable256[n >> 16 & 255] + BitsSetTable256[n >> 24]
for _ in range(int(sys.stdin.readline())):
	initialize()
	(n, q) = map(int, sys.stdin.readline().split())
	arr = list(map(int, sys.stdin.readline().split()))
	even = 0
	odd = 0
	for i in range(n):
		if countSetBits(arr[i]) & 1:
			odd += 1
		else:
			even += 1
	for i in range(q):
		a = int(sys.stdin.readline())
		if countSetBits(a) & 1:
			sys.stdout.write(f'{odd} {even}\n')
		else:
			sys.stdout.write(f'{even} {odd}\n')


t = int(input())
for j in range(t):
	(n, q) = map(int, input().split())
	l = list(map(int, input().split()))
	e = o = 0
	m = []
	for i in l:
		if bin(i).count('1') % 2 == 0:
			e += 1
		else:
			o += 1
	a = str(e) + ' ' + str(o)
	b = str(o) + ' ' + str(e)
	for i in range(q):
		p = int(input())
		m.append(p)
	for i in range(q):
		if bin(m[i]).count('1') % 2 == 0:
			print(a)
		else:
			print(b)


from sys import stdin
t = int(stdin.readline())
while t > 0:
	n = list(map(int, stdin.readline().split()))
	a = list(map(int, stdin.readline().split()))
	e = 0
	o = 0
	for i in range(0, n[0]):
		if str(bin(a[i])).count('1') % 2 == 0:
			e += 1
		else:
			o += 1
	while n[1] > 0:
		e1 = 0
		o1 = 0
		q = int(stdin.readline())
		if str(bin(q)).count('1') % 2 == 0:
			e1 = e
			o1 = o
		else:
			e1 = o
			o1 = e
		print(e1, o1)
		n[1] = n[1] - 1
	t = t - 1


for T in range(int(input())):
	(n, q) = map(int, input().split())
	l = list(map(int, input().split()))
	(even, qu) = (0, [])
	for i in range(n):
		if bin(l[i]).count('1') % 2 == 0:
			even += 1
	str1 = str(even) + ' ' + str(n - even)
	str2 = str(n - even) + ' ' + str(even)
	for i in range(q):
		qu.append(int(input()))
	for i in range(q):
		print(str1) if bin(qu[i]).count('1') % 2 == 0 else print(str2)


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')


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 & 15
		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)


import sys
for qwe in range(int(sys.stdin.readline())):
	(n, q) = list(map(int, sys.stdin.readline().split()))
	L = list(map(int, sys.stdin.readline().split()))
	even = 0
	odd = 0
	for i in range(n):
		x = bin(L[i]).count('1')
		if x % 2 == 0:
			even += 1
		else:
			odd += 1
	for asdea in range(q):
		p = int(sys.stdin.readline())
		ans1 = even
		ans2 = odd
		if bin(p).count('1') % 2 == 1:
			(ans1, ans2) = (ans2, ans1)
		print(str(ans1) + ' ' + str(ans2))


t = int(input())
for _ in range(t):
	(c, d) = (0, 0)
	(n, q) = map(int, input().split())
	l = list(map(int, input().split()))
	k = [int(input()) for i in range(q)]
	for i in l:
		if bin(i).count('1') % 2 == 0:
			c = c + 1
		else:
			d = d + 1
	for i in k:
		if bin(i).count('1') % 2 == 0:
			print(c, d)
		else:
			print(d, c)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, q) = [int(i) for i in input().split()]
	arr = [int(i) for i in input().split()]
	e = 0
	o = 0
	for i in arr:
		x = bin(i)[2:].count('1')
		if x & 1 == 0:
			e += 1
		else:
			o += 1
	for i in range(q):
		p = int(input())
		m = bin(p)[2:].count('1')
		if m % 2 == 0:
			print(e, o)
		else:
			print(o, e)


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)


import os, io, sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	res = [0, 0]
	for j in arr:
		res[bin(j).count('1') % 2] += 1
	for _ in range(q):
		cnt = bin(int(input())).count('1')
		print(*res) if not cnt % 2 else print(*res[::-1])


import sys
for testcase in range(int(sys.stdin.readline())):
	(a, b) = map(int, sys.stdin.readline().split())
	a = list(map(int, sys.stdin.readline().split()))
	even = 0
	odd = 0
	for i in a:
		if bin(i).count('1') % 2 == 0:
			even = even + 1
		else:
			odd = odd + 1
	for i in range(b):
		p = int(sys.stdin.readline())
		if bin(p).count('1') % 2 == 0:
			print(str(even) + ' ' + str(odd))
		else:
			print(str(odd) + ' ' + str(even))


import sys
for _ in range(int(input())):
	(n, q) = map(int, sys.stdin.readline().rstrip().split())
	b = list(map(int, sys.stdin.readline().rstrip().split()))
	q1 = 0
	q2 = 0
	for i in b:
		if bin(i).count('1') % 2 == 0:
			q1 += 1
		else:
			q2 += 1
	for _ in range(q):
		q = int(sys.stdin.readline())
		if bin(q).count('1') % 2 == 0:
			s = str(q1) + ' ' + str(q2)
		else:
			s = str(q2) + ' ' + str(q1)
		sys.stdout.write(s)
		sys.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 & 255] + Bit[n >> 8 & 255] + Bit[n >> 16 & 255] + 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)


import sys
t = int(sys.stdin.readline().rstrip())
while t:
	(N, Q) = [int(x) for x in sys.stdin.readline().rstrip().split()]
	A = [int(x) for x in sys.stdin.readline().rstrip().split()]
	c = 0
	for i in range(N):
		if bin(A[i]).count('1') % 2 == 0:
			c += 1
	co = N - c
	for i in range(Q):
		p = int(sys.stdin.readline().rstrip())
		p = bin(p).count('1')
		if p % 2 == 0:
			string = str(c) + ' ' + str(co) + '\n'
			sys.stdout.write(string)
		else:
			string = str(co) + ' ' + str(c) + '\n'
			sys.stdout.write(string)
	t = t - 1


import sys
input = sys.stdin.readline

def main():
	for _ in range(int(input())):
		(n, q) = [int(a) for a in input().split()]
		numbers = list(map(int, input().split()))
		evens = 0
		for j in numbers:
			if bin(j).count('1') % 2 == 0:
				evens += 1
		for __ in range(q):
			if bin(int(input())).count('1') % 2 == 0:
				print(evens, n - evens)
			else:
				print(n - evens, evens)
main()


import os, io, sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	l = list(map(int, input().split()))
	o = 0
	e = 0
	for i in l:
		x = bin(i)[2:].count('1')
		if x % 2 == 0:
			e += 1
		else:
			o += 1
	for i in range(q):
		c = int(input())
		x = bin(c)[2:].count('1')
		if x % 2 == 0:
			print(e, o)
		else:
			print(o, e)


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)


from sys import stdin, stdout
import math
from collections import Counter, deque
L = lambda : list(map(int, stdin.readline().strip().split()))
M = lambda : map(int, stdin.readline().strip().split())
I = lambda : int(stdin.readline().strip())
IN = lambda : stdin.readline().strip()
C = lambda : stdin.readline().strip().split()
mod = 1000000007

def s(a):
	print(' '.join(list(map(str, a))))
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 & 255] + Bit[n >> 8 & 255] + Bit[n >> 16 & 255] + Bit[n >> 24]
initialize()
for _ in range(I()):
	(n, q) = M()
	a = L()
	(e, o) = (0, 0)
	for i in range(n):
		x = countsetbits(a[i])
		if x % 2 == 0:
			e += 1
		else:
			o += 1
	for i in range(q):
		p = I()
		if countsetbits(p) % 2 == 0:
			print(e, o)
		else:
			print(o, e)


for t in range(int(input())):
	(n, q) = map(int, input().split())
	qu = []
	lst = list(map(int, input().split()))
	evnbt = 0
	oddbt = 0
	for i in lst:
		if bin(i).count('1') % 2 == 0:
			evnbt += 1
		else:
			oddbt += 1
	str1 = str(evnbt) + ' ' + str(oddbt)
	str2 = str(oddbt) + ' ' + str(evnbt)
	for i in range(q):
		p = int(input())
		qu.append(p)
	for i in qu:
		if bin(i).count('1') % 2 == 0:
			print(str1)
		else:
			print(str2)


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)


import sys

def binary(x):
	x = bin(int(x)).count('1')
	if x % 2:
		return 0
	else:
		return 1
for _ in range(int(sys.stdin.readline())):
	(a, b) = map(int, sys.stdin.readline().split())
	s = list(map(binary, sys.stdin.readline().split()))
	even = sum(s)
	odd = a - even
	for j in range(b):
		x = bin(int(sys.stdin.readline())).count('1')
		if x % 2:
			print(odd, even)
		else:
			print(even, odd)


import sys
for _ in range(int(sys.stdin.readline())):
	(n, q) = map(int, sys.stdin.readline().split())
	arr = list(map(int, sys.stdin.readline().split()))
	(even, odd) = (0, 0)
	for i in arr:
		if bin(i).count('1') % 2:
			odd += 1
		else:
			even += 1
	for _ in range(q):
		k = int(sys.stdin.readline())
		if bin(k).count('1') % 2 == 0:
			print(even, odd)
		else:
			print(odd, even)


import sys
T = int(sys.stdin.readline().strip())
for i in range(T):
	(n, q) = [int(X) for X in sys.stdin.readline().strip().split()]
	arr = [int(X) for X in sys.stdin.readline().strip().split()]
	count_even = 0
	for i in arr:
		if bin(i).count('1') % 2 == 0:
			count_even += 1
	count_odd = n - count_even
	for z in range(q):
		p = int(sys.stdin.readline().strip())
		if bin(p).count('1') % 2 == 0:
			string = str(count_even) + ' ' + str(count_odd) + '\n'
			sys.stdout.write(string)
		else:
			string = str(count_odd) + ' ' + str(count_even) + '\n'
			sys.stdout.write(string)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	od = ev = 0
	for j in arr:
		if bin(j).count('1') % 2 == 0:
			ev += 1
		else:
			od += 1
	que = [int(input()) for i in range(q)]
	for i in que:
		if bin(i).count('1') % 2 == 0:
			print(ev, od)
		else:
			print(od, ev)


import sys

def xor_engine():
	t = int(sys.stdin.readline().strip())
	for _ in range(t):
		(n, q) = map(int, sys.stdin.readline().strip().split())
		numbers = list(map(int, sys.stdin.readline().strip().split()))
		(numbers_even_ones_count, numbers_odd_ones_count) = (0, 0)
		for number in numbers:
			if bin(number).count('1') % 2 == 0:
				numbers_even_ones_count += 1
		numbers_odd_ones_count = n - numbers_even_ones_count
		for ___ in range(q):
			p = int(sys.stdin.readline().strip())
			if numbers_odd_ones_count == numbers_even_ones_count:
				sys.stdout.write(f'{numbers_even_ones_count} {numbers_odd_ones_count}\n')
				continue
			are_p_ones_even = bin(p).count('1') % 2 == 0
			if are_p_ones_even:
				sys.stdout.write(f'{numbers_even_ones_count} {numbers_odd_ones_count}\n')
			else:
				sys.stdout.write(f'{numbers_odd_ones_count} {numbers_even_ones_count}\n')
xor_engine()


try:
	from sys import stdin, stdout
	for _ in range(int(input())):
		(n, k) = map(int, stdin.readline().split())
		a = list(map(int, stdin.readline().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(stdin.readline())
			count_of_i = bin(q).count('1')
			if count_of_i % 2 == 0:
				print(even, odd)
			else:
				print(odd, even)
except:
	pass