You are given a simple code of a function and you would like to know what it will return. 

F(N, K, Answer, Operator, A[N]) returns int;
begin
for i=1..K do
for j=1..N do
Answer=(Answer operator A_{j})
return Answer
end

Here N, K, Answer and the value returned by the function F are integers; A is an array of N integers numbered from 1 to N; Operator can be one of the binary operators XOR, AND or OR. If you are not familiar with these terms then better have a look at following articles: XOR, OR, AND.

------ Input ------ 

The first line of input contains an integer T - the number of test cases in file. Description of each test case consists of three lines. The first one contains three integers N, K and initial Answer. Array A is given in the second line and Operator is situated on the third one. Operators are given as strings, of capital letters. It is guaranteed that there will be no whitespaces before or after Operator. 

------ Output ------ 

Output one line for each test case - the value that is returned by described function with given arguments.

------ Constraints ------ 

$1≤T≤100
$$1≤N≤1000
$0≤Answer, K, A_{i}≤10^{9}
Operator is one of these: "AND", "XOR", "OR".

----- Sample Input 1 ------ 
3
3 1 0
1 2 3
XOR
3 1 0
1 2 3
AND
3 1 0
1 2 3
OR
----- Sample Output 1 ------ 
0
0
3
----- explanation 1 ------ 
0 xor 1 xor 2 xor 3 = 0
0 and 1 and 2 and 3 = 0
0 or 1 or 2 or 3 = 3

Difficulty: MEDIUM_HARD
Tags: Mathematics

Bit manipulation

Implementation
Skill types: Bit manipulation

Starter code:

Solutions:
def fnc(n, k, answer, s, a):
	for i in range(k):
		for j in range(n):
			if s == 'XOR':
				answer ^= a[j]
			elif s == 'OR':
				answer |= a[j]
			else:
				answer &= a[j]
	return answer
t = int(input())
for T in range(t):
	(n, k, answer) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	s = input().strip()
	if s == 'XOR':
		k %= 2
	else:
		k = min(k, 1)
	print(fnc(n, k, answer, s, a))


t = int(input())
for i in range(t):
	(n, k, ans) = map(int, input().split())
	a1 = [int(x) for x in input().split()]
	s = input()
	if not k:
		print(ans)
	else:
		if s[0] == 'X':
			if k % 2 == 0:
				pass
			else:
				for j in a1:
					ans = ans ^ j
		elif s[0] == 'A':
			for j in a1:
				ans = ans & j
		else:
			for j in a1:
				ans = ans | j
		print(ans)


t = int(input())
while t > 0:
	(n, k, a) = map(int, input().split())
	l = list(map(int, input().split()))
	s = input().strip()
	if k > 0:
		if s == 'XOR':
			if k % 2 != 0:
				for i in l:
					a ^= i
		elif s == 'AND':
			for i in l:
				a &= i
		else:
			for i in l:
				a |= i
	print(a)
	t -= 1


T = int(input())
for i in range(T):
	(n, k, ans) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	b = input()
	if k == 0:
		print(ans)
	else:
		if b[0] == 'A':
			for i in a:
				ans &= i
		elif b[0] == 'O':
			for i in a:
				ans |= i
		elif k % 2:
			for i in a:
				ans ^= i
		print(ans)


for _ in range(int(input())):
	(n, k, a) = map(int, input().split())
	l = list(map(int, input().split()))
	s = input()
	if k == 0:
		print(a)
	else:
		if s[0] == 'X':
			if k % 2 == 0:
				pass
			else:
				for j in l:
					a = a ^ j
		elif s[0] == 'A':
			for j in l:
				a = a & j
		else:
			for j in l:
				a = a | j
		print(a)


def f(N, K, ans, A, str1):
	if str1 == 'XOR':
		if K > 0:
			if K % 2 == 1:
				for j in range(N):
					ans = ans ^ A[j]
	elif str1 == 'AND':
		if K > 0:
			for j in range(N):
				ans = ans & A[j]
	elif K > 0:
		for j in range(N):
			ans = ans | A[j]
	return ans
for _ in range(int(input())):
	(n, k, a) = map(int, input().strip().split())
	A = list(map(int, input().strip().split()))
	s = input().strip()
	print(f(n, k, a, A, s))


def f(N, K, A, op, arr):
	if K == 0:
		return A
	orig = A
	for j in range(N):
		if op == 'XOR':
			A = A ^ arr[j]
		elif op == 'AND':
			A = A & arr[j]
		elif op == 'OR':
			A = A | arr[j]
	if op == 'XOR' and K % 2 == 0:
		return orig
	return A
t = int(input())
for _ in range(t):
	(N, K, A) = list(map(int, input().strip().split()))
	arr = list(map(int, input().strip().split()))
	op = input().strip()
	ans = f(N, K, A, op, arr)
	print(ans)


import sys
T = int(sys.stdin.readline())
Ans = ''
for t in range(T):
	(N, k, Answer) = map(int, sys.stdin.readline().split())
	A = list(map(int, sys.stdin.readline().split()))
	Q = sys.stdin.readline().split()
	for item in Q:
		if item[0] == 'A' or item[0] == 'O' or item[0] == 'X':
			op = item
			break
	if k == 0:
		Ans += str(Answer) + '\n'
		continue
	key = A[0]
	if op[0] == 'X':
		for i in range(1, N):
			key = key ^ A[i]
	elif op[0] == 'O':
		for i in range(1, N):
			key = key | A[i]
	else:
		for i in range(1, N):
			key = key & A[i]
	if op[0] == 'A':
		Ans += str(Answer & key) + '\n'
	elif op[0] == 'O':
		Ans += str(Answer | key) + '\n'
	elif k % 2 == 1:
		Ans += str(Answer ^ key) + '\n'
	else:
		Ans += str(Answer) + '\n'
sys.stdout.write(Ans)


__author__ = 'Ronald Kaiser'
__email__ = 'raios dot catodicos at gmail dot com'
(OR, XOR, AND) = ('OR', 'XOR', 'AND')
f = {XOR: lambda x, y: x ^ y, AND: lambda x, y: x & y, OR: lambda x, y: x | y}
for _ in range(int(input())):
	(N, K, ans) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	o = input().strip()
	if K == 0 or (o == XOR and K % 2 == 0):
		print(ans)
		continue
	x = A[0]
	for i in range(1, N):
		x = f[o](x, A[i])
	print(f[o](x, ans))


T = int(input())
ans = []
for _ in range(T):
	(N, K, Ans) = [int(i) for i in input().split()]
	A = [int(i) for i in input().split()]
	S = input().strip()
	if S == 'XOR':
		x = A[0]
		for i in range(1, N):
			x ^= A[i]
		if K % 2 != 0:
			Ans ^= x
	elif S == 'AND':
		x = A[0]
		for i in range(1, N):
			x &= A[i]
		if K != 0:
			Ans &= x
	elif S == 'OR':
		x = A[0]
		for i in range(1, N):
			x |= A[i]
		if K != 0:
			Ans |= x
	ans.append(Ans)
for i in ans:
	print(i)


__author__ = 'star-lord'

def calc(n, k, ans, op, array):
	if k == 0 or (k % 2 == 0 and op == 'XOR'):
		return ans
	else:
		for element in array:
			if op == 'XOR':
				ans ^= element
			elif op == 'AND':
				ans &= element
			else:
				ans |= element
		return ans
testCase = int(input())
while testCase > 0:
	(n, k, ans) = map(int, input().strip().split())
	array = map(int, input().strip().split())
	operator = input().strip()
	print(calc(n, k, ans, operator, array))
	testCase -= 1


__author__ = 'Ronald Kaiser'
__email__ = 'raios dot catodicos at gmail dot com'
from operator import xor, and_, or_
f = {'XOR': xor, 'AND': and_, 'OR': or_}
for _ in range(int(input())):
	(N, K, ans) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	o = input().strip()
	if K == 0 or (o == 'XOR' and K % 2 == 0):
		print(ans)
		continue
	x = A[0]
	for i in range(1, N):
		x = f[o](x, A[i])
	print(f[o](x, ans))


t = int(input())
while t:
	(n, k, ans) = map(int, input().strip().split())
	a = list(map(int, input().strip().split()))
	operator = input().strip()
	if operator == 'XOR':
		if k > 0:
			if k % 2 == 0:
				ans = ans ^ 0
			else:
				for j in range(n):
					ans = ans ^ a[j]
	elif operator == 'AND':
		if k > 0:
			for j in range(n):
				ans = ans & a[j]
	elif operator == 'OR':
		if k > 0:
			for j in range(n):
				ans = ans | a[j]
	print(ans)
	t -= 1


T = int(input())
for t in range(T):
	(N, K, Answer) = map(int, input().split())
	A = map(int, input().split())
	Operator = input().rstrip()
	if K:
		for a in A:
			if Operator == 'AND':
				Answer &= a
			if Operator == 'XOR' and K % 2:
				Answer ^= a
			if Operator == 'OR':
				Answer |= a
	print(Answer)


for _ in range(int(input())):
	(n, k, ans) = map(int, input().split())
	a = list(map(int, input().split()))
	op = input().strip()
	if k == 0:
		print(ans)
	else:
		if op == 'AND':
			for i in range(n):
				ans = ans & a[i]
		elif op == 'OR':
			for i in range(n):
				ans = ans | a[i]
		elif k % 2 == 0:
			pass
		else:
			for i in range(n):
				ans = ans ^ a[i]
		print(ans)


test = int(input())
for t in range(test):
	(a, b, answer) = map(int, input().strip().split())
	seanswerond = list(map(int, input().strip().split()))
	operation = input().strip()
	if b == 0 or (b % 2 == 0 and operation == 'XOR'):
		print(answer)
	else:
		for i in seanswerond:
			if operation == 'XOR':
				answer = answer ^ i
			elif operation == 'OR':
				answer = answer | i
			else:
				answer = answer & i
		print(answer)


from sys import stdin, stdout

def sin():
	return stdin.readline().rstrip()

def listInput():
	return list(map(int, sin().split()))

def printBS(li):
	if not li:
		return
	for i in range(len(li) - 1):
		stdout.write('%d ' % li[i])
	stdout.write('%d\n' % li[-1])
t = int(sin())
for _ in range(t):
	(n, k, ans) = listInput()
	li = listInput()
	op = sin()
	if op == 'AND':
		if k != 0:
			for i in li:
				ans = ans & i
	elif op == 'OR':
		if k != 0:
			for i in li:
				ans = ans | i
	elif k % 2 == 1:
		for i in li:
			ans = ans ^ i
	print(ans)


import operator

def F(K, answer, op, A):
	for k in range(K):
		for a in A:
			answer = op(answer, a)
	return answer
for t in range(int(input())):
	(N, K, answer) = map(int, input().split())
	A = list(map(int, input().split()))
	operator_name = input().strip()
	fun = None
	if operator_name == 'AND':
		fun = operator.and_
		K = min(K, 1)
	elif operator_name == 'OR':
		fun = operator.or_
		K = min(K, 1)
	elif operator_name == 'XOR':
		fun = operator.xor
		K %= 2
	print(F(K, answer, fun, A))


def main():
	from sys import stdin, stdout
	from functools import reduce
	from operator import xor, and_, or_
	inp = stdin.readline
	out = stdout.write
	res = []
	t = int(inp().strip())
	for _ in range(t):
		(n, k, ans) = map(int, inp().strip().split())
		a = list(map(int, inp().strip().split()))
		op = input()
		if not k or (not k & 1 and op[0] == 'X'):
			res.append(str(ans) + '\n')
		else:
			for i in a:
				if op[0] == 'X':
					ans ^= i
				elif op[0] == 'A':
					ans &= i
				else:
					ans |= i
			res.append(str(ans) + '\n')
	for i in range(t):
		out(res[i])
main()


t = int(input())
for z in range(t):
	(N, K, Answer) = map(int, input().split())
	A = map(int, input().split())
	operator = input().strip()
	if K:
		for a in A:
			if operator == 'OR':
				Answer = Answer | a
			elif operator == 'XOR' and K % 2:
				Answer = Answer ^ a
			elif operator == 'AND':
				Answer = Answer & a
	print(Answer)


test = int(input())
for _ in range(test):
	(n, k, answer) = map(int, input().split())
	array = list(map(int, input().split()))
	operator = input()
	if k == 0:
		print(answer)
	else:
		if operator[0] == 'X':
			if k % 2 == 0:
				pass
			else:
				for i in array:
					answer = answer ^ i
		elif operator[0] == 'A':
			for i in array:
				answer = answer & i
		else:
			for i in array:
				answer = answer | i
		print(answer)


import functools
for _ in range(int(input())):
	(n, k, ans) = map(int, input().split())
	l = list(map(int, input().split()))
	op = input().strip()
	if k > 0:
		if op[0] == 'A':
			for i in range(len(l)):
				ans = ans & l[i]
			print(ans)
		elif op[0] == 'O':
			for i in range(len(l)):
				ans = ans | l[i]
			print(ans)
		elif k % 2 == 0:
			print(ans)
		else:
			for i in range(len(l)):
				ans = ans ^ l[i]
			print(ans)
	elif k == 0:
		print(ans)


for _ in range(int(input())):
	(N, K, Ans) = map(int, input().split())
	A = list(map(int, input().split()))
	oper = input()
	Ans_0 = Ans
	oper = oper.strip()
	if K % 2 == 0:
		m = 2
	else:
		m = 1
	if oper == 'AND':
		for j in range(m):
			for i in range(N):
				Ans = Ans & A[i]
	elif oper == 'OR':
		for j in range(m):
			for i in range(N):
				Ans = Ans | A[i]
	elif oper == 'XOR':
		for j in range(m):
			for i in range(N):
				Ans = Ans ^ A[i]
	if K != 0:
		print(Ans)
	else:
		print(Ans_0)


t = int(input())
for i in range(t):
	(x, k, answer) = map(int, input().split())
	a = map(int, input().split())
	op = input().strip()
	if k:
		for i in a:
			if op == 'AND':
				answer &= i
			if op == 'OR':
				answer |= i
			if op == 'XOR' and k % 2:
				answer ^= i
	print(answer)


from functools import reduce
t = int(input())
while t:
	(n, k, ans) = map(int, input().strip().split())
	a = list(map(int, input().strip().split()))
	operator = input().strip()
	if operator == 'XOR':
		m = reduce(lambda c, d: c ^ d, a)
		if k > 0:
			if k % 2 == 0:
				ans = ans ^ 0
			else:
				ans = ans ^ m
	elif operator == 'AND':
		m = reduce(lambda c, d: c & d, a)
		if k > 0:
			ans = ans & m
	elif operator == 'OR':
		m = reduce(lambda c, d: c | d, a)
		if k > 0:
			ans = ans | m
	print(ans)
	t -= 1


def solve():
	(n, k, answer) = map(int, input().split())
	array = list(map(int, input().split()))
	operator = input()
	if k == 0:
		print(answer)
	else:
		if operator[0] == 'X':
			if k % 2 == 0:
				pass
			else:
				for i in array:
					answer = answer ^ i
		elif operator[0] == 'A':
			for i in array:
				answer = answer & i
		else:
			for i in array:
				answer = answer | i
		print(answer)
t = int(input())
while t != 0:
	solve()
	t -= 1


for t in range(0, int(input())):
	(n, k, ans) = map(int, input().strip().split())
	arr = list(map(int, input().strip().split()))
	ops = input().strip()
	if k == 0 or (k % 2 == 0 and ops == 'XOR'):
		print(ans)
	else:
		for i in arr:
			if ops == 'XOR':
				ans ^= i
			elif ops == 'OR':
				ans |= i
			else:
				ans &= i
		print(ans)


testcases = int(input())
while testcases != 0:
	(N, K, answer) = list(map(int, input().split()))
	inputArray = list(map(int, input().split()))
	operat = input()
	if K == 0:
		print(answer)
	elif K % 2 == 0 and operat[0] == 'X':
		print(answer)
	else:
		if operat[0] == 'X':
			for j in range(N):
				answer ^= inputArray[j]
		elif operat[0] == 'A':
			for j in range(N):
				answer &= inputArray[j]
		else:
			for j in range(N):
				answer |= inputArray[j]
		print(answer)
	testcases -= 1


for _ in range(int(input())):
	(n, k, a) = map(int, input().split())
	l = list(map(int, input().split()))
	s = input().strip()
	if k == 0:
		print(a)
	else:
		if s == 'AND':
			for x in l:
				a = a & x
		elif s == 'OR':
			for x in l:
				a = a | x
		elif s == 'XOR':
			if k % 2 != 0:
				for x in l:
					a = a ^ x
		print(a)


import sys

def input():
	return sys.stdin.readline().strip()

def iinput():
	return int(input())

def rinput():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))
for _ in range(iinput()):
	(n, k, ans) = rinput()
	a = get_list()
	b = input()
	if k == 0:
		print(ans)
	else:
		if b[0] == 'A':
			for i in a:
				ans &= i
		elif b[0] == 'O':
			for i in a:
				ans |= i
		elif k % 2:
			for i in a:
				ans ^= i
		print(ans)


for _ in range(int(input())):
	(_, k, ans) = map(int, input().split())
	a = map(int, input().split())
	op = input()
	if not k or (not k & 1 and op[0] == 'X'):
		print(ans)
	else:
		for n in a:
			if op[0] == 'X':
				ans ^= n
			elif op[0] == 'O':
				ans |= n
			else:
				ans &= n
		print(ans)


from functools import reduce
ops = {'XOR': lambda x, y: x ^ y, 'AND': lambda x, y: x & y, 'OR': lambda x, y: x | y}
for _ in range(int(input())):
	(n, k, ans) = map(int, input().split())
	arr = list(map(int, input().split()))
	op = input().strip()
	tot = reduce(ops[op], arr)
	if k == 0:
		print(ans)
		continue
	if op == 'XOR':
		if k % 2 == 0:
			print(ans)
		else:
			print(ans ^ tot)
	elif op == 'AND':
		print(ans & tot)
	else:
		print(ans | tot)


mod = 1000000007
read_int = lambda : int(input().strip())
read_str = lambda : input().strip()
read_str_arr = lambda : input().strip().split()
read_int_arr = lambda : [int(x) for x in input().strip().split()]

def apply_op(op, A, n, ans):
	for i in range(n):
		if op == 'AND':
			ans &= A[i]
		elif op == 'OR':
			ans |= A[i]
		elif op == 'XOR':
			ans ^= A[i]
		else:
			raise
	return ans

def solve():
	(n, k, ans) = read_int_arr()
	A = read_int_arr()
	op = read_str()
	if k == 0:
		print(ans)
	elif op == 'XOR' and k & 1 == 0:
		print(ans)
	else:
		print(apply_op(op, A, n, ans))
for _ in range(int(input())):
	solve()


def F(n, k, answer, op, a):
	if k == 0:
		return answer
	op_cal = a[0]
	if op == 'XOR':
		for i in a[1:]:
			op_cal = op_cal ^ i
		if k % 2 == 0:
			op_cal = 0
		answer = answer ^ op_cal
	elif op == 'AND':
		for i in a[1:]:
			op_cal = op_cal & i
		answer = answer & op_cal
	elif op == 'OR':
		for i in a[1:]:
			op_cal = op_cal | i
		answer = answer | op_cal
	return answer
t = int(input())
for i in range(t):
	(n, k, answer) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	op = input().strip()
	print(F(n, k, answer, op, a))


for _ in range(int(input())):
	(n, k, answer) = map(int, input().split())
	a = list(map(int, input().split()))
	o = input()
	if k == 0:
		print(answer)
	else:
		if o[0] == 'X':
			if k % 2:
				for i in range(n):
					answer ^= a[i]
		elif o[0] == 'O':
			for i in range(n):
				answer |= a[i]
		else:
			for i in range(n):
				answer &= a[i]
		print(answer)


for tc in range(int(input().strip())):
	(N, K, Ans) = map(int, input().strip().split())
	A = [int(x) for x in input().strip().split()]
	op = input().strip()
	for i in A:
		if K > 0:
			if op == 'AND':
				Ans = Ans & i
			elif op == 'OR':
				Ans = Ans | i
			elif K & 1 == 1:
				Ans = Ans ^ i
	print(Ans)


t = int(input())
for T in range(t):
	(n, k, ans) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	s = input().strip()
	if k > 0:
		if s == 'OR' or s == 'AND':
			for i in a:
				if s == 'OR':
					ans |= i
				elif s == 'AND':
					ans &= i
		elif k % 2 == 0:
			pass
		else:
			for i in a:
				ans ^= i
	print(ans)


def main():
	import operator

	def g(N, K, A, operation, answer):
		if K:
			operation = operation.rstrip()
			if operation == 'XOR':
				K = K % 2
				operation = operation = operator.xor
			elif operation == 'OR':
				operation = operator.or_
				K = 1
			else:
				operation = operator.and_
				K = 1
			for i in range(K):
				for j in A:
					answer = operation(answer, j)
		return answer
	for T in range(int(input())):
		(N, K, answer) = map(int, input().split())
		A = map(int, input().split())
		operation = input()
		print(g(N, K, A, operation, answer))
main()


for _ in range(int(input())):
	(n, k, answer) = map(int, input().split())
	a = [int(item) for item in input().split()]
	s = input().strip()
	if k == 0:
		print(answer)
	else:
		if s == 'AND':
			for i in range(n):
				answer = answer & a[i]
		elif s == 'OR':
			for i in range(n):
				answer = answer | a[i]
		elif k % 2 == 0:
			pass
		else:
			for i in range(n):
				answer = answer ^ a[i]
		print(answer)


T = int(input())
for t in range(T):
	(n, k, ans) = map(int, input().split())
	arr = list(map(int, input().split()))
	op = input().strip()
	if op == 'XOR':
		k = k % 2
		for j in range(k):
			for i in range(n):
				ans ^= arr[i]
	else:
		k = min(1, k)
		for j in range(k):
			for i in range(n):
				if op == 'AND':
					ans &= arr[i]
				else:
					ans |= arr[i]
	print(ans)


for _ in range(int(input())):
	(n, k, a) = map(int, input().split())
	arr = map(int, input().split())
	oper = input()
	if not k:
		print(a)
	else:
		if oper[0] == 'X':
			if k % 2 == 0:
				pass
			else:
				for j in arr:
					a = a ^ j
		elif oper[0] == 'A':
			for j in arr:
				a = a & j
		else:
			for j in arr:
				a = a | j
		print(a)