Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef lent some money to Chefexim. He has been asking for his money back for a long time, but Chefexim always comes up with an excuse. This time, Chef got really angry, since he needed the money to buy some ingredients for his ladoos, and Chefexim decided to return the money he borrowed. Knowing Chef's love of challenges, Chefexim gave Chef a challenge along with the money in order to keep him calm and happy.

Chefexim divided the money he borrowed from Chef into $N$ bags (numbered $1$ through $N$); for each valid $i$, the $i$-th bag contains $A_{i}$ units of money. Then, he gave all $N$ bags to Chef along with two integers $K$ and $X$. Now, Chef may perform the following operation any number of times (including zero):
Pick exactly $K$ different bags with numbers $i_{1}, i_{2}, \ldots, i_{K}$ ($1 ≤ i_{j} ≤ N$ for each valid $j$).
Change the amounts of money inside the selected bags. For each $j$ ($1 ≤ j ≤ K$), the amount of money inside the $i_{j}$-th bag is changed from $A_{i_{j}}$ to $A_{i_{j}} \oplus X$. Here, $\oplus$ denotes the bitwise XOR operation.

Each bag may be picked any number of times in different operations.

Find the maximum total amount of money (sum of amounts of money in all the bags) Chef can have at the end if he performs the operations optimally.

------  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 a single integer $N$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$ denoting the initial amounts of money inside the bags.
The third line contains a single integer $K$.
The fourth line contains a single integer $X$.

------  Output ------
For each test case, print a single line containing one integer — the maximum amount of money Chef can have.

------  Constraints  ------
$1 ≤ T ≤ 100$
$1 ≤ N ≤ 10^{4}$
$1 ≤ K ≤ N$
$0 ≤ A_{i} ≤ 10^{9}$ for each valid $i$
$0 ≤ X ≤ 10^{9}$

------  Subtasks ------
Subtask #1 (10 points): $1 ≤ N ≤ 10$

Subtask #2 (10 points):
$1 ≤ N ≤ 100$
$0 ≤ A_{i} ≤ 1$ for each valid $i$
$0 ≤ X ≤ 1$

Subtask #3 (80 points): original constraints

----- Sample Input 1 ------ 
2

5

1 2 3 4 5

2

4

7

10 15 20 13 2 1 44

4

14
----- Sample Output 1 ------ 
23

129
----- explanation 1 ------ 
Example case 1: Chef can perform two operations.
1. Pick the bags $1$ and $4$, change the amount of money in bag $1$ to $1 \oplus 4 = 5$ and the amount of money in bag $4$ to $4 \oplus 4 = 0$. After this operation, the sequence $A = (5, 2, 3, 0, 5)$.
2. Pick the bags $2$ and $3$, change the amount of money in bag $2$ to $2 \oplus 4 = 6$ and the amount of money in bag $3$ to $3 \oplus 4 = 7$. After this operation, $A = (5, 6, 7, 0, 5)$.

At the end, the total amount of money is $5+6+7+0+5 = 23$, which is maximum possible.

Example case 2: Chef can pick the bags $1$, $3$, $5$ and $6$, change the amount of money in bag $1$ to $10 \oplus 14 = 4$, the amount of money in bag $3$ to $20 \oplus 14 = 26$, the amount of money in bag $5$ to $2 \oplus 14 = 12$ and the amount of money in bag $6$ to $1 \oplus 14 = 15$. Afterwards, $A = (4, 15, 26, 13, 12, 15, 44)$ and the total amount of money is $129$, which is maximum possible.

Difficulty: HARD
Tags: Bit manipulation

Mathematics

Greedy algorithms
Skill types: Bit manipulation

Greedy algorithms

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	k = int(input())
	x = int(input())
	ans1 = sum(a)
	if k == n:
		ans2 = 0
		for i in a:
			ans2 += i ^ x
		print(max(ans1, ans2))
		continue
	delta = 0
	diff = []
	eles = 0
	for i in a:
		val = (i ^ x) - i
		if val > 0:
			delta += val
			eles += 1
		diff.append(val)
	if eles % 2 and k % 2 == 0:
		x = float('inf')
		for i in diff:
			x = min(x, abs(i))
		delta -= x
	print(ans1 + delta)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	k = int(input())
	x = int(input())
	val = 0
	summation = 0
	if k == n or x == 0:
		for v in a:
			val += v ^ x
			summation += v
		print(max(val, summation))
		continue
	cnt = 0
	ans = 0
	for v in a:
		ans += max(v ^ x, v)
		if v ^ x >= v:
			cnt += 1
	if k % 2 == 0 and cnt % 2 == 1:
		mi = 10 ** 18
		for v in a:
			temp = (v ^ x) - v
			if temp >= 0:
				mi = min(mi, temp)
		mx = -10 ** 18
		for v in a:
			temp = (v ^ x) - v
			if temp <= 0:
				mx = max(mx, temp)
		print(max(ans - mi, ans + mx))
		continue
	print(ans)


def test():
	n = int(input())
	a = list(map(int, input().split()))
	ans = sum(a)
	k = int(input())
	x = int(input())
	d = [(a[i] ^ x) - a[i] for i in range(n)]
	d.sort(reverse=True)
	pre = [0 for i in range(n + 1)]
	pre[0] = 0
	for i in range(1, n + 1):
		pre[i] = pre[i - 1] + d[i - 1]
	c = 0
	for i in range(n):
		if d[i] > 0:
			c += 1
	i = 0
	j = k
	sm = 0
	while i < j:
		dd = j - i
		kk = c // dd
		kk = kk * dd
		sm = max(sm, pre[kk])
		if dd + kk <= n:
			sm = max(sm, pre[dd + kk])
		i += 1
		j -= 1
		if k == n:
			break
	ans += sm
	print(ans)
tt = int(input())
for _ in range(tt):
	test()


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	k = int(input())
	x = int(input())
	a.sort(key=lambda i: i - (i ^ x))
	if k == n:
		print(max(sum(a), sum((i ^ x for i in a))))
		continue
	if k % 2 == 0:
		r = 0
		i = 0
		while 2 * i + 1 < n:
			p = (a[2 * i] ^ x) + (a[2 * i + 1] ^ x)
			q = a[2 * i] + a[2 * i + 1]
			r += max(p, q)
			i += 1
		if n % 2 == 1:
			r += a[-1]
		print(r)
	else:
		print(sum((max(i, i ^ x) for i in a)))


for _ in range(int(input())):
	n = int(input())
	l = [int(n) for n in input().split()]
	s1 = sum(l)
	k = int(input())
	x = int(input())
	c = 0
	lp = []
	ln = []
	for i in l:
		r = (x ^ i) - i
		if r >= 0:
			c += 1
			lp.append(r)
		else:
			ln.append(r)
	nm = 0
	pm = 0
	sp = 0
	sn = 0
	if len(lp) > 0:
		sp = sum(lp)
		pm = min(lp)
	if len(ln) > 0:
		sn = sum(ln)
		nm = max(ln)
	if k == n:
		print(max(s1, s1 + sp + sn))
	elif k % 2 == 1:
		print(max(sp + s1, s1))
	elif c % 2 == 0:
		print(sp + s1)
	elif c < n:
		print(max(s1 + sp - pm, s1 + sp + nm, s1))
	else:
		print(max(s1 + sp - pm, s1))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	k = int(input())
	x = int(input())
	if n == k:
		s1 = 0
		s2 = 0
		for i in range(n):
			s1 += a[i]
			s2 += a[i] ^ x
		print(max(s1, s2))
		continue
	if k % 2 == 1:
		s1 = 0
		for i in range(n):
			s1 += max(a[i], a[i] ^ x)
		print(s1)
	else:
		l = []
		for i in range(n):
			l.append((a[i] ^ x) - a[i])
		l.sort(reverse=True)
		s1 = sum(a)
		best = 0
		diff = 0
		for i in range(n):
			diff += l[i]
			if i % 2 == 1 and diff > best:
				best = diff
		print(s1 + best)


def func(x):
	return x - (x ^ g)
g = -1
m = 0
t = int(input())
for _ in range(0, t):
	n = int(input())
	l = list(map(int, input().split()))
	k = int(input())
	x = int(input())
	g = x
	m = 0
	a = sorted(l, key=func)
	b = list()
	for i in range(0, n):
		b.append(a[i] ^ x)
	s = 0
	c = 0
	if k == n:
		print(max(sum(a), sum(b)))
		continue
	elif k % 2 == 0:
		i = 0
		while i + 1 < n:
			if b[i] + b[i + 1] > a[i] + a[i + 1]:
				s = s + b[i] + b[i + 1]
				c = i + 2
			i = i + 2
		s = s + sum(a[c:])
		print(s)
	else:
		i = 0
		while i < n:
			if b[i] > a[i]:
				s = s + b[i]
			else:
				s = s + a[i]
			i = i + 1
		print(s)


tcase = int(input())
while tcase > 0:
	tcase -= 1
	n = int(input())
	l = list(map(int, input().split()))
	k = int(input())
	x = int(input())
	s = sum(l)
	if k == n:
		s1 = 0
		for i in range(n):
			value = x ^ l[i]
			s1 += value
		if s1 > s:
			print(s1)
		else:
			print(s)
	else:
		(diff_list, cnt_inc) = ([], 0)
		for i in range(n):
			value = x ^ l[i]
			if value > l[i]:
				s += value - l[i]
				cnt_inc += 1
			diff_list.append(int(abs(value - l[i])))
		if k % 2 == 0 and cnt_inc % 2 == 1:
			s -= min(diff_list)
		print(s)


import sys
for _ in range(int(input())):
	n = int(input())
	a = [int(y) for y in input().split()]
	k = int(input())
	x = int(input())
	if x == 0:
		print(sum(a))
		continue
	b = [y ^ x for y in a]
	if k == n:
		print(max(sum(b), sum(a)))
		continue
	s = 0
	dif = [0] * n
	mi = sys.maxsize
	ma = -mi - 1
	pos = 0
	for i in range(n):
		dif[i] = b[i] - a[i]
		s += a[i]
		if dif[i] < 0:
			if dif[i] > ma:
				ma = dif[i]
		else:
			pos += 1
			s += dif[i]
			if dif[i] < mi:
				mi = dif[i]
	if k % 2 == 0 and pos % 2 != 0:
		if ma + mi > 0:
			s += ma
		else:
			s -= mi
	print(s)


for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	k = int(input())
	x = int(input())
	s1 = sum(arr)
	jt = []
	if n != k:
		count = 0
		for i in arr:
			xor = i ^ x
			if xor - i > 0:
				s1 = s1 + (xor - i)
				count += 1
			jt.append(abs(xor - i))
		if k % 2 == 0:
			if count % 2 != 0:
				print(s1 - min(jt))
			else:
				print(s1)
		else:
			print(s1)
	else:
		for i in range(0, len(arr)):
			jt.append(arr[i] ^ x)
		s2 = sum(jt)
		if s2 > s1:
			print(s2)
		else:
			print(s1)


t = int(input())
while t:
	t -= 1
	n = int(input())
	arr = list(map(int, input().strip().split()))
	k = int(input())
	x = int(input())
	m = []
	notm = []
	for ele in arr:
		if ele ^ x > ele:
			m.append(ele)
		else:
			notm.append(ele)
	temp = sum(notm)
	for ele in m:
		temp += ele ^ x
	if n == k:
		sum1 = 0
		for ele in arr:
			sum1 += ele ^ x
		print(max(sum1, sum(arr)))
	elif len(m) % 2 == 1 and k % 2 == 0:
		profitdiff = 10 ** 100
		errordiff = 10 ** 100
		for ele in m:
			if abs(ele - (ele ^ x)) < profitdiff:
				profitdiff = abs(ele - (ele ^ x))
		for ele in notm:
			if abs(ele - (ele ^ x)) < errordiff:
				errordiff = abs(ele - (ele ^ x))
		print(max(temp - errordiff, temp - profitdiff))
	else:
		print(temp)


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	k = int(input())
	x = int(input())
	l = []
	for i in a:
		xx = i ^ x
		l.append(xx - i)
	if k == n:
		print(max(sum(a), sum(a) + sum(l)))
		continue
	ans = sum(a)
	count = 0
	for j in l:
		if j > 0:
			ans += j
			count += 1
	if k % 2 == 0 and count % 2 == 1:
		r = 10000000000000
		for j in l:
			r = min(r, abs(j))
		ans -= r
	print(ans)


def debug(A, X):
	for i in A:
		print(i, '--', i ^ X)
for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	k = int(input())
	X = int(input())
	P = []
	N = []
	for i in A:
		if i ^ X > i:
			P.append(i)
		else:
			N.append(i)
	m = len(P)
	temp = sum(N)
	for i in P:
		temp += i ^ X
	if n == k:
		temp = 0
		for i in A:
			temp += i ^ X
		print(max(temp, sum(A)))
	elif m % 2 == 1 and k % 2 == 0:
		mn = 999999999999
		mp = 999999999999
		for i in N:
			if mn > i - (i ^ X):
				mn = i - (i ^ X)
		for i in P:
			if mp > (i ^ X) - i:
				mp = (i ^ X) - i
		print(max(temp - mn, temp - mp))
	else:
		print(temp)


from collections import defaultdict
T = int(input())
for test in range(T):
	N = int(input())
	A = [int(v) for v in input().split()]
	K = int(input())
	X = int(input())
	smallest_gain = float('inf')
	smallest_loss = -float('inf')
	base = 0
	total_gain = 0
	total_loss = 0
	pos_count = 0
	for m in A:
		base += m
		change = X - 2 * (m & X)
		if change > 0:
			total_gain += change
			pos_count += 1
			if change < smallest_gain:
				smallest_gain = change
		else:
			total_loss += change
			if change > smallest_loss:
				smallest_loss = change
	if K == N:
		print(max(base + total_gain + total_loss, base))
		continue
	if K & 1 or pos_count % 2 == 0:
		print(base + total_gain)
		continue
	elif smallest_loss + smallest_gain > 0:
		print(base + total_gain + smallest_loss)
	else:
		print(base + total_gain - smallest_gain)


import sys

def read_line():
	return sys.stdin.readline()[:-1]

def read_int():
	return int(sys.stdin.readline())

def read_int_line():
	return [int(v) for v in sys.stdin.readline().split()]
T = read_int()
for _test in range(T):
	N = read_int()
	A = read_int_line()
	K = read_int()
	X = read_int()
	if X == 0 or K == N:
		ans1 = 0
		ans2 = 0
		for v in A:
			ans1 += v
			ans2 += v ^ X
		print(max(ans1, ans2))
		continue
	K %= 2
	ans = 0
	cnt = 0
	for v in A:
		val = max(v, v ^ X)
		ans += val
		if val == v ^ X:
			cnt += 1
	if K == 0 and cnt % 2 == 1:
		rem = 10 ** 18
		for x in A:
			v = (x ^ X) - x
			if v >= 0:
				rem = min(rem, v)
		add = -10 ** 18
		for x in A:
			v = (x ^ X) - x
			if v <= 0:
				add = max(add, v)
		ans = max(ans - rem, ans + add)
	print(ans)


t = int(input())
for T in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	k = int(input())
	x = int(input())
	(s1, s2) = (0, 0)
	l = []
	if k == n:
		for i in range(n):
			s1 += a[i]
			s2 += a[i] ^ x
		print(max(s1, s2))
	elif k % 2 != 0:
		for i in range(n):
			s1 += max(a[i], a[i] ^ x)
		print(s1)
	else:
		for i in range(n):
			l.append((a[i] ^ x) - a[i])
		l.sort(reverse=True)
		s1 = sum(a)
		(h, diff) = (0, 0)
		for i in range(n):
			diff += l[i]
			if i % 2 == 1 and diff > h:
				h = diff
		print(s1 + h)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	k = int(input())
	x = int(input())
	s = sum(a)
	if k == n:
		b = [i ^ x for i in a]
		s = max(s, sum(b))
	else:
		d = [(i ^ x) - i for i in a]
		d.sort(reverse=True)
		if k % 2 == 1:
			for i in d:
				if i > 0:
					s += i
		else:
			for i in range(0, n - 1, 2):
				ss = d[i] + d[i + 1]
				if ss > 0:
					s += ss
	print(s)


try:
	t = int(input())
	for i in range(t):
		n = int(input())
		ls = list(map(int, input().split(' ')))
		k = int(input())
		x = int(input())
		s = sum(ls)
		xor_list = []
		for j in ls:
			xor_list.append((j ^ x) - j)
		xor_list = sorted(xor_list)
		pos = 0
		index = len(xor_list) - 1
		while index >= 0 and xor_list[index] > 0:
			pos += 1
			index -= 1
		mainls = []
		if k % 2 == 0 and pos % 2 != 0:
			if n >= k + 1:
				if pos + 1 <= n:
					mainls = [pos - 1, pos + 1]
				else:
					mainls = [pos - 1]
			else:
				mainls = [0, n]
		elif n >= k + 1:
			mainls = [pos]
		else:
			mainls = [0, n]
		possible_answers = []
		for j in mainls:
			start_index = n - j
			num = 0
			for k in range(start_index, n):
				num += xor_list[k]
			possible_answers.append(num)
		possible_answers.append(0)
		print(s + max(possible_answers))
except Exception as e:
	pass


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	k = int(input())
	x = int(input())
	b = []
	for j in range(n):
		b.append((a[j] ^ x) - a[j])
	b.sort()
	ptr = 0
	while ptr < n and b[ptr] <= 0:
		ptr += 1
	c = n - ptr
	val = 0
	for i in range(ptr, n):
		val += b[i]
	if k == n:
		print(max(sum(a) + sum(b), sum(a)))
	elif c == n:
		if c % 2 == 0 or k % 2 != 0:
			print(sum(a) + val)
		else:
			print(sum(a) + val - b[ptr])
	elif k % 2 == 0:
		if c % 2 == 0:
			print(sum(a) + val)
		else:
			print(max(sum(a) + val - b[ptr], sum(a) + val + b[ptr - 1]))
	else:
		print(sum(a) + val)


testcase = int(input())
for _ in range(testcase):
	N = int(input())
	l1 = [int(x) for x in input().split()]
	k = int(input())
	x = int(input())
	if k == N:
		s1 = s2 = 0
		for i in l1:
			s1 += i
			s2 += i ^ x
		print(max(s1, s2))
	elif k % 2 == 0:
		l2 = [(i ^ x) - i for i in l1]
		l2.sort(reverse=True)
		diff = best = 0
		for i in range(N):
			diff += l2[i]
			if i % 2 == 1 and diff > best:
				best = diff
		print(sum(l1) + best)
	else:
		s = 0
		for i in l1:
			s += max(i, i ^ x)
		print(s)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	k = int(input())
	x = int(input())
	diff = []
	xor = []
	count = 0
	ans = sum(a)
	for i in range(n):
		if (a[i] ^ x) - a[i] > 0:
			count += 1
			ans += (a[i] ^ x) - a[i]
		diff.append((a[i] ^ x) - a[i])
		xor.append(a[i] ^ x)
	diff.sort(reverse=True)
	mval = 100000000000
	for i in diff:
		mval = min(mval, abs(i))
	if k < n:
		if count % 2 != 0 and k % 2 == 0:
			print(ans - mval)
		else:
			print(ans)
	else:
		print(max(sum(a), sum(xor)))


t = int(input())
for _ in range(t):
	n = int(input())
	arr = sorted(list(map(int, input().split())))
	k = int(input())
	x = int(input())
	count = 0
	add_arr = sum(arr)
	profit = [0] * n
	for (index, i) in enumerate(arr):
		c = (i ^ x) - i
		profit[index] = c
		if c > 0:
			count += 1
	profit = sorted(profit, reverse=True)
	add_profit = sum(profit)
	if k == n:
		print(max(add_arr, add_arr + add_profit))
	elif count % 2 == 0 or k % 2 == 1:
		print(add_arr + sum(profit[:count]))
	else:
		increment = 0
		if count < n:
			increment = profit[count - 1] + profit[count]
		print(max(add_arr + sum(profit[:count - 1]), add_arr + sum(profit[:count - 1]) + increment))


t = int(input())
for i in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	s = sum(l)
	d = list()
	k = int(input())
	x = int(input())
	d = [(j ^ x) - j for j in l]
	d.sort(reverse=True)
	sd = sum(d)
	if n == k:
		if sd > 0:
			s += sd
	elif k % 2 == 0:
		for j in range(0, n - 1, 2):
			ss = sum(d[j:j + 2])
			if ss > 0:
				s += ss
	else:
		for j in range(n):
			if d[j] > 0:
				s += d[j]
	print(s)


t = int(input())
while t:
	t = t - 1
	n = int(input())
	a = []
	arr = []
	b = []
	sum1 = 0
	sum2 = 0
	sum = 0
	arr = list(map(int, input().split()))
	k = int(input())
	x = int(input())
	for i in range(n):
		sum = sum + arr[i]
	dict1 = []
	dict2 = []
	for i in range(n):
		d = []
		x1 = x ^ arr[i]
		if x1 >= arr[i]:
			d.append(x1)
			d.append(i)
			dict1.append(d)
		else:
			d.append(x1)
			d.append(i)
			dict2.append(d)
	l1 = len(dict1)
	l2 = len(dict2)
	for i in range(l1):
		a.append(dict1[i][0] - arr[dict1[i][1]])
	for i in range(l2):
		b.append(arr[dict2[i][1]] - dict2[i][0])
	a.sort()
	b.sort()
	if l1 == 0:
		print(sum)
	elif k == n:
		for i in range(l1):
			sum1 = sum1 + a[i]
		for i in range(l2):
			sum2 = sum2 + b[i]
		if sum1 >= sum2:
			for i in range(l1):
				sum = sum + dict1[i][0] - arr[dict1[i][1]]
			for i in range(l2):
				sum = sum - arr[dict2[i][1]] + dict2[i][0]
			print(sum)
		else:
			print(sum)
	elif k % 2 == 0:
		if n > k:
			if l1 % 2 == 0 or l1 % k == 0:
				for i in range(l1):
					sum = sum + dict1[i][0] - arr[dict1[i][1]]
				print(sum)
			elif l2 == 0:
				for i in range(l1):
					sum = sum + dict1[i][0] - arr[dict1[i][1]]
				print(sum - a[0])
			elif a[0] >= b[0]:
				for i in range(l1):
					sum = sum + dict1[i][0] - arr[dict1[i][1]]
				print(sum - b[0])
			else:
				for i in range(l1):
					sum = sum + dict1[i][0] - arr[dict1[i][1]]
				print(sum - a[0])
	else:
		for i in range(l1):
			sum = sum + dict1[i][0] - arr[dict1[i][1]]
		print(sum)


T = int(input())
for ieq in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	K = int(input())
	X = int(input())
	xored = []
	diffs = []
	for a in A:
		xored.append(a ^ X)
	sum1 = sum(A)
	for i in range(N):
		diffs.append(xored[i] - A[i])
	if N == K:
		print(max(sum1, sum(xored)))
		continue
	if K % 2 == 1:
		s1 = 0
		for i in range(N):
			s1 += max(A[i], A[i] ^ X)
		print(s1)
	else:
		diffs.sort(reverse=True)
		best = 0
		diff = 0
		for i in range(N):
			diff += diffs[i]
			if i % 2 == 1 and diff > best:
				best = diff
		print(sum1 + best)


t = int(input())
for _ in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	k = int(input())
	x = int(input())
	sum = 0
	sum1 = 0
	sum2 = 0
	for i in a:
		sum2 = sum2 + i
	if n == k:
		for i in a:
			sum = sum + i
			sum1 = sum1 + (x ^ i)
		print(max(sum, sum1))
	elif k % 2 != 0:
		for i in a:
			sum = sum + max(i, x ^ i)
		print(max(sum, sum2))
	else:
		defe = 0
		best = 0
		d = []
		for i in a:
			d.append((x ^ i) - i)
		d.sort()
		d.reverse()
		for i in range(0, len(d)):
			j = d[i]
			defe = defe + j
			if i % 2 == 1:
				best = max(best, defe)
		for i in a:
			best = best + i
		print(max(best, sum2))


t = int(input())
for test in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	k = int(input())
	x = int(input())
	pos = []
	neg = []
	ans = sum(arr)
	for i in range(n):
		xx = (arr[i] ^ x) - arr[i]
		if xx >= 0:
			pos.append(xx)
		else:
			neg.append(xx)
	if k == n:
		temp = 0
		for i in range(n):
			temp += (arr[i] ^ x) - arr[i]
		if temp > 0:
			ans += temp
		print(ans)
		continue
	elif k % 2 == 1:
		print(ans + sum(pos))
		continue
	else:
		pos = sorted(pos, reverse=True)
		neg = sorted(neg, reverse=True)
		temp = 0
		if len(pos) % 2:
			temp += sum(pos[0:len(pos) - 1])
			if len(neg) > 0:
				yy = pos[-1] + neg[0]
				if yy > 0:
					temp += yy
		else:
			temp += sum(pos)
		print(ans + temp)


t = int(input())
while t:
	n = int(input())
	ar = list(map(int, input().split()))
	k = int(input())
	x = int(input())
	change = []
	for i in range(n):
		temp = (ar[i] ^ x) - ar[i]
		change.append(temp)
	change.sort(reverse=True)
	summ = 0
	i = 0
	if k == n:
		summ = max(0, sum(change))
	elif k % 2 == 0:
		step = 2
		while i <= n - step:
			if sum(change[i:i + step]) > 0:
				summ += sum(change[i:i + step])
				for z in range(i, i + step):
					change[z] = -1 * change[z]
			i += step
		change.sort(reverse=True)
		while i <= n - step:
			if sum(change[i:i + step]) > 0:
				summ += sum(change[i:i + step])
				for z in range(i, i + step):
					change[z] = -1 * change[z]
			i += step
	else:
		step = 1
		while i <= n - step:
			if sum(change[i:i + step]) > 0:
				summ += sum(change[i:i + step])
			else:
				break
			i += step
	print(sum(ar) + summ)
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	k = int(input())
	x = int(input())
	sum1 = 0
	sum2 = 0
	if n == k:
		sum1 = sum(arr)
		for i in range(n):
			sum2 += arr[i] ^ x
		ans = max(sum1, sum2)
	elif k % 2 == 1:
		for i in range(n):
			sum1 += max(arr[i], arr[i] ^ x)
		ans = sum1
	else:
		differnece_arr = []
		for i in range(n):
			differnece_arr.append((arr[i] ^ x) - arr[i])
		differnece_arr.sort(reverse=True)
		sum1 = sum(arr)
		greatest = 0
		difference = 0
		for i in range(n):
			difference += differnece_arr[i]
			if i % 2 == 1 and difference > greatest:
				greatest = difference
		ans = sum1 + greatest
	print(ans)


a = int(input())
for i in range(a):
	n = int(input())
	b = [int(i) for i in input().split()]
	k = int(input())
	x = int(input())
	c = [0] * len(b)
	d = [0] * len(b)
	for i in range(len(b)):
		c[i] = (b[i] ^ x) - b[i]
	for i in range(len(b)):
		d[i] = b[i] ^ x
	c.sort(reverse=True)
	ctr1 = 0
	ctr2 = 0
	for i in range(len(c)):
		if c[i] > 0:
			ctr1 += 1
		else:
			ctr2 += 1
	hold = 0
	for j in range(ctr1):
		hold += c[j]
	if k % 2 == 0 and ctr1 % 2 == 0 and (k < n):
		print(sum(b) + hold)
	elif k % 2 == 0 and ctr1 % 2 == 1 and (k < n):
		if ctr1 < len(c):
			print(sum(b) + max(hold - c[ctr1 - 1], hold + c[ctr1]))
		else:
			print(sum(b) + hold - c[ctr1 - 1])
	elif k % 2 == 1 and ctr1 % 2 == 0 and (k < n):
		print(sum(b) + hold)
	elif k % 2 == 1 and ctr1 % 2 == 1 and (k < n):
		print(sum(b) + hold)
	elif k == n:
		print(max(sum(b), sum(b) + sum(c)))


for t in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	j = int(input())
	x = int(input())
	d = []
	summ = cnt = 0
	for i in l:
		d.append((i ^ x) - i)
	d.sort(reverse=True)
	for i in d:
		if i >= 0:
			cnt += 1
		else:
			break
	if j == n:
		s1 = sum(d)
		s2 = sum(l)
		if s1 > 0:
			print(s1 + s2)
		else:
			print(s2)
	elif j % 2 == 0:
		if cnt % 2 == 0:
			summ += sum(d[:cnt])
		else:
			summ += sum(d[:cnt - 1])
			if cnt + 1 <= n:
				if summ + d[cnt - 1] + d[cnt] > summ:
					summ += d[cnt - 1] + d[cnt]
		print(summ + sum(l))
	elif j % 2 == 1:
		for i in d:
			if i >= 0:
				summ += i
			else:
				break
		print(summ + sum(l))


t = int(input())
for tc in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	k = int(input())
	x = int(input())
	if k == n:
		sm = xsum = 0
		for i in range(n):
			sm += a[i]
			xsum += a[i] ^ x
		print(max(sm, xsum))
		continue
	mdec = minc = 10 ** 15
	sm = 0
	xsum = 0
	linc = 0
	for i in range(n):
		if a[i] < a[i] ^ x:
			minc = min(minc, (a[i] ^ x) - a[i])
			xsum += a[i] ^ x
			linc += 1
		else:
			mdec = min(mdec, a[i] - (a[i] ^ x))
			sm += a[i]
	if linc % 2 == 0 or (linc + k) % 2 == 0:
		print(sm + xsum)
	elif linc != n:
		print(xsum + sm - min(mdec, minc))
	else:
		print(xsum - minc)


t = int(input())

def solve(n, lista, k, x):
	suma = sum(lista)
	listb = [i ^ x for i in lista]
	sumb = sum(listb)
	(diffarr, cnt) = ([], 0)
	for i in range(n):
		diffarr.append(lista[i] - listb[i])
		if lista[i] - listb[i] < 0:
			cnt += 1
	if n == k:
		if suma > sumb:
			print(suma)
		else:
			print(sumb)
	else:
		(syssum, val) = (0, 9999999999999999999999999)
		for i in range(n):
			val = min(val, abs(diffarr[i]))
			if diffarr[i] > 0:
				syssum += lista[i]
			else:
				syssum += listb[i]
		if k % 2 == 1:
			print(syssum)
		elif cnt % 2 == 1:
			print(syssum - val)
		else:
			print(syssum)
for test in range(t):
	n = int(input())
	lista = [int(i) for i in input().split()]
	k = int(input())
	x = int(input())
	solve(n, lista, k, x)


test = int(input())
for _ in range(test):
	n = int(input())
	arr = list(map(int, input().split()))
	k = int(input())
	x = int(input())
	if x == 0:
		print(sum(arr))
	elif n == k:
		sum1 = sum(arr)
		brr = [h ^ x for h in arr]
		sum2 = sum(brr)
		print(max(sum1, sum2))
	else:
		pr = []
		mr = []
		for q in arr:
			w = (q ^ x) - q
			if w > 0:
				pr.append(w)
			else:
				mr.append(w)
		ml = len(mr)
		pl = len(pr)
		sm = 0
		if pl > 0:
			if pl % 2 == 0 or k % 2 == 1:
				sm += sum(pr)
			else:
				temp1 = min(pr)
				sm += sum(pr) - temp1
				if ml > 0:
					temp2 = max(mr)
					if temp1 + temp2 >= 0:
						sm += temp2 + temp1
		print(sum(arr) + sm)


t = input()
t = int(t)
for i in range(t):
	n = input()
	n = int(n)
	A = list(map(int, input().split()))
	k = input()
	k = int(k)
	x = input()
	x = int(x)
	A_sum = sum(A)
	if n == k:
		tempSum = 0
		for j in range(n):
			temp = A[j] ^ x
			tempSum += temp
		if A_sum < tempSum:
			print(tempSum)
		else:
			print(A_sum)
	else:
		times = 0
		tempSum = A_sum
		Min = 9999999999999
		for j in range(n):
			temp = A[j] ^ x
			if temp - A[j] > 0:
				tempSum += temp - A[j]
				times += 1
			if abs(temp - A[j]) < Min:
				Min = abs(temp - A[j])
		if k % 2 == 0 and times % 2 != 0:
			print(tempSum - Min)
		else:
			print(tempSum)


t = int(input())
for i in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	dx = []
	k = int(input())
	x = int(input())
	dx = [(j ^ x) - j for j in l]
	dx.sort(reverse=True)
	sd = int(sum(dx))
	s = int(sum(l))
	if n == k:
		if sd > 0:
			s += sd
	elif k % 2 == 0:
		s1 = s
		s2 = s
		s3 = s
		v = 0
		for j in range(n):
			if dx[j] > 0:
				v += 1
		if v % 2 != 0:
			r = 0
			while r < v - 1:
				s1 += dx[r]
				r += 1
				s2 = s1
			if v + 1 <= n:
				while r < v + 1:
					s2 += dx[r]
					r += 1
			s = max(s1, s2, s3)
		else:
			r = 0
			while r < v:
				s += dx[r]
				r += 1
	else:
		r = 0
		while r < n and dx[r] > 0:
			s += dx[r]
			r += 1
	print(s)


def solve():
	n = int(input())
	A = [int(a) for a in input().split()]
	k = int(input())
	x = int(input())
	ans = 0
	B = []
	for i in range(n):
		B.append((x ^ A[i]) - A[i])
		ans += A[i]
	if k == n:
		t = 0
		for i in range(n):
			t += B[i]
		return max(ans, ans + t)
	B.sort(reverse=True)
	m = n
	for i in range(n):
		if B[i] < 0:
			m = i
			break
		else:
			ans += B[i]
	if m % k == 0 or m % 2 == 0 or k % 2 == 1:
		return ans
	if m == n:
		return ans - B[m - 1]
	return max(ans - B[m - 1], ans + B[m])
t = int(input())
for x in range(t):
	print(solve())


T = int(input())
for i in range(T):
	N = int(input())
	l = list(map(int, input().split()))
	K = int(input())
	X = int(input())
	l2 = []
	for j in range(N):
		l2.append((X ^ l[j]) - l[j])
	l2.sort()
	l2.reverse()
	count = 0
	if N == K:
		if count < sum(l2[:K]):
			count = sum(l2[:K])
	else:
		d = len(l2)
		for j in range(len(l2)):
			if l2[j] < 0:
				d = j
				break
		if K % 2 == 0:
			c = d // 2
			if 2 * c + 2 <= N:
				count = max(count, sum(l2[:2 * c]), sum(l2[:2 * c + 2]))
			else:
				count = max(count, sum(l2[:2 * c]))
		elif sum(l2[:d]) > count:
			count = sum(l2[:d])
	print(count + sum(l))


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	k = int(input())
	x = int(input())
	(count, ans1, ans2, ans, neg) = (0, 0, 0, 0, 44)
	(diff, countp) = ([], 0)
	for i in range(n):
		count += arr[i]
		if x ^ arr[i] > arr[i]:
			diff.append((x ^ arr[i]) - arr[i])
			countp += 1
		elif neg == 44:
			neg = (x ^ arr[i]) - arr[i]
		elif (x ^ arr[i]) - arr[i] > neg:
			neg = (x ^ arr[i]) - arr[i]
	diff.sort(reverse=True)
	if k == n:
		ans1 = count
		for i in range(n):
			ans1 += (x ^ arr[i]) - arr[i]
		if ans1 > count:
			ans = ans1
		else:
			ans = count
	elif k % 2 == 0:
		if countp % 2:
			for i in range(len(diff) - 1):
				ans1 += diff[i]
			if neg != 44:
				ans2 = ans1 + diff[len(diff) - 1] + neg
			if ans1 > ans2:
				count += ans1
			else:
				count += ans2
			ans = count
		else:
			for i in range(len(diff)):
				count += diff[i]
			ans = count
	else:
		for i in range(len(diff)):
			count += diff[i]
		ans = count
	print(ans)


import math
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	k = int(input())
	x = int(input())
	diff_negative = []
	dif_positive = []
	c = 0
	SALSAL = 0
	sn = 0
	if k == n:
		fir = sum(l)
		sec = 0
		for i in l:
			sec = sec + (i ^ x)
		print(max(fir, sec))
	if k < n:
		for i in l:
			xo = i - (i ^ x)
			SALSAL = SALSAL + i
			if xo < 0:
				diff_negative.append(xo)
				dif_positive.append(-xo)
				c = c + 1
				sn = sn - xo
			else:
				dif_positive.append(xo)
		mi = min(dif_positive)
		if k % 2 == 0:
			if (c + k) % 2 == 0:
				ANSWER = SALSAL + sn
			else:
				ANSWER = SALSAL + sn
				ANSWER = ANSWER - mi
		else:
			ANSWER = sn + SALSAL
		print(ANSWER)


T = int(input())
for t in range(T):
	n = int(input())
	l = input()
	l = list(map(int, l.split(' ')))
	k = int(input())
	x = int(input())
	s = sum(l)
	num0 = 0
	mlist = []
	xlist = []
	mindiff = 1000000000
	for i in range(n):
		mlist.append(max(l[i] ^ x, l[i]))
		xlist.append(l[i] ^ x)
		if l[i] ^ x > l[i]:
			num0 += 1
		if mindiff > abs((l[i] ^ x) - l[i]):
			mindiff = abs((l[i] ^ x) - l[i])
	if k == n:
		print(max(sum(l), sum(xlist)))
	elif k % 2 == 1:
		print(sum(mlist))
	elif num0 % 2 == 0:
		print(sum(mlist))
	else:
		print(sum(mlist) - mindiff)


t = int(input())
for zxc in range(t):
	a = int(input())
	l = list(map(int, input().split()))
	m = int(input())
	b = int(input())
	s = sum(l)
	l1 = []
	if a != m:
		count = 0
		for i in l:
			p = i ^ b
			if p - i > 0:
				s = s + (p - i)
				count += 1
			l1.append(abs(p - i))
		if m % 2 == 0 and count % 2 != 0:
			print(s - min(l1))
		else:
			print(s)
	else:
		x = []
		for i in range(0, len(l)):
			x.append(l[i] ^ b)
		sum1 = sum(x)
		if sum1 > s:
			print(sum1)
		else:
			print(s)


for i in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	k = int(input())
	x = int(input())
	arr1 = []
	arr2 = []
	for i in arr:
		arr1.append(i ^ x)
	for i in range(len(arr)):
		arr2.append(arr1[i] - arr[i])
	arr3 = sorted(arr2, reverse=True)
	if k == n:
		if sum(arr3) > 0:
			x = sum(arr3) + sum(arr)
			print(x)
		else:
			print(sum(arr))
	if k % 2 == 0 and k != n:
		sum1 = 0
		for i in range(0, len(arr) - 1, 2):
			sum2 = 0
			sum2 += arr3[i] + arr3[i + 1]
			if sum2 > 0:
				sum1 += sum2
		print(sum1 + sum(arr))
	if k % 2 != 0 and k != n:
		sum1 = sum(arr)
		for i in arr3:
			if i > 0:
				sum1 += i
		print(sum1)


T = int(input())
for j in range(T):
	N = int(input())
	A = list(map(int, input().split(' ')))
	K = int(input())
	X = int(input())
	B = []
	C = []
	countit = 0
	diffarr = []
	for i in A:
		B.append(i ^ X)
		if i ^ X > i:
			C.append(i ^ X)
			countit += 1
		else:
			C.append(i)
	for i in range(len(A)):
		diffarr.append(abs(A[i] - B[i]))
	if N != K:
		if countit % 2 != 0 and K % 2 == 0:
			print(sum(C) - min(diffarr))
		else:
			print(sum(C))
	else:
		print(max(sum(A), sum(B)))


for _ in range(int(input())):
	(mx, s1, s2, s3) = (0, 0, 0, 0)
	n = int(input())
	l = [int(i) for i in input().split()]
	s1 = sum(l)
	k = int(input())
	xor = int(input())
	l1 = [i ^ xor for i in l]
	l2 = [l1[i] - l[i] for i in range(n)]
	l2.sort()
	l2 = l2[::-1]
	if n == k:
		print(max(sum(l1), sum(l)))
	else:
		if k % 2 == 0:
			for i in range(n):
				s2 += l2[i]
				if i % 2 == 1:
					mx = max(mx, s2)
		else:
			for i in range(n):
				s3 += l2[i]
				mx = max(mx, s3)
		print(sum(l) + mx)


def solve5(a, n, m, k, x):
	sol1 = 0
	if len(m) < k:
		if len(m) % 2 == 0:
			dp = [0] * n
			for i in range(len(m)):
				dp[m[i][1]] = 1
			for i in range(n):
				if dp[i] == 1:
					sol1 += a[i] ^ x
				else:
					sol1 += a[i]
			return max(sol1, 0)
		else:
			m.sort(key=lambda q: q[0], reverse=True)
			dp = [0] * n
			for i in range(len(m) - 1):
				dp[m[i][1]] = 1
			for i in range(n):
				if dp[i] == 1:
					sol1 += a[i] ^ x
				else:
					sol1 += a[i]
			ans = sol1
			sol1 = 0
			m.sort(key=lambda q: q[0], reverse=True)
			dp = [0] * n
			for i in range(len(m)):
				dp[m[i][1]] = 1
			gg = []
			for i in range(n):
				if dp[i] == 1:
					sol1 += a[i] ^ x
				else:
					gg.append((a[i] - (a[i] ^ x), i))
					sol1 += a[i]
			gg.sort(key=lambda q: q[0])
			if len(gg) > 0:
				sol1 += (a[gg[0][1]] ^ x) - a[gg[0][1]]
				return max(sol1, ans)
			else:
				return max(ans, 0)
	if len(m) >= k:
		if len(m) % 2 == 1 and k % 2 == 0:
			m.sort(key=lambda q: q[0], reverse=True)
			dp = [0] * n
			for i in range(len(m) - 1):
				dp[m[i][1]] = 1
			sum1 = 0
			for i in range(n):
				if dp[i] == 1:
					sum1 += a[i] ^ x
				else:
					sum1 += a[i]
			sol1 = 0
			m.sort(key=lambda q: q[0], reverse=True)
			dp = [0] * n
			for i in range(len(m)):
				dp[m[i][1]] = 1
			gg = []
			for i in range(n):
				if dp[i] == 1:
					sol1 += a[i] ^ x
				else:
					gg.append((a[i] - (a[i] ^ x), i))
					sol1 += a[i]
			gg.sort(key=lambda q: q[0])
			if len(gg) > 0:
				sol1 += (a[gg[0][1]] ^ x) - a[gg[0][1]]
				return max(sum1, sol1)
			else:
				return max(sum1, 0)
		else:
			full = 0
			dp = [0] * n
			for i in range(len(m)):
				dp[m[i][1]] = 1
			for i in range(n):
				if dp[i] == 1:
					full += a[i] ^ x
				else:
					full += a[i]
			return max(full, 0)
t = int(input())
for cc in range(t):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	k = int(input())
	x = int(input())
	if k == n:
		sum1 = 0
		for i in range(n):
			sum1 += a[i] ^ x
		print(max(sum1, sum(a)))
		continue
	else:
		m = []
		meow = []
		sum3 = 0
		for i in range(n):
			if a[i] < a[i] ^ x:
				m.append(((a[i] ^ x) - a[i], i))
				sum3 += (a[i] ^ x) - a[i]
			if a[i] <= a[i] ^ x:
				meow.append(((a[i] ^ x) - a[i], i))
		if len(m) == 0:
			print(sum(a))
			continue
		elif len(m) % k == 0:
			dp = [0] * n
			sum1 = 0
			for i in range(len(m)):
				dp[m[i][1]] = 1
			for i in range(n):
				if dp[i] == 1:
					sum1 += a[i] ^ x
				else:
					sum1 += a[i]
			print(max(sum1, sum(a)))
		elif len(meow) % k == 0:
			dp = [0] * n
			sum1 = 0
			for i in range(len(meow)):
				dp[meow[i][1]] = 1
			for i in range(n):
				if dp[i] == 1:
					sum1 += a[i] ^ x
				else:
					sum1 += a[i]
			print(max(sum1, sum(a)))
		elif len(m) < k:
			b = []
			c = []
			for i in range(n):
				if a[i] ^ x > a[i]:
					b.append(a[i])
				else:
					c.append(a[i])
			b = b + c
			for i in range(k):
				b[i] = b[i] ^ x
			mota = []
			for i in range(n):
				if b[i] ^ x > b[i]:
					mota.append(((b[i] ^ x) - b[i], i))
			ans3 = solve5(b, n, mota, k, x)
			ans5 = solve5(a, n, m, k, x)
			ans6 = solve5(a, n, meow, k, x)
			print(max(sum(a), ans5, ans6, ans3))
		else:
			b = []
			c = []
			mota = []
			for i in range(n):
				if a[i] ^ x > a[i]:
					b.append(a[i])
				else:
					c.append(a[i])
			b = b + c
			for i in range(k):
				b[i] = b[i] ^ x
			for i in range(n):
				if b[i] ^ x > b[i]:
					mota.append(((b[i] ^ x) - b[i], i))
			ans3 = solve5(b, n, mota, k, x)
			ans5 = solve5(a, n, m, k, x)
			ans6 = solve5(a, n, meow, k, x)
			print(max(sum(a), ans5, ans6, ans3))


t = int(input())
while t > 0:
	n = int(input())
	l = [int(x) for x in input().split()]
	k = int(input())
	x = int(input())
	xorpos = []
	xorneg = []
	for i in l:
		a = (i ^ x) - i
		if a > 0:
			xorpos.append(a)
		else:
			xorneg.append(a)
	p = xorpos.__len__()
	neg = xorneg.__len__()
	if k == 1:
		print(sum(l) + sum(xorpos))
	elif k == n:
		q = sum(l) + sum(xorpos) + sum(xorneg)
		print(max(sum(l), q))
	elif k % 2 == 0:
		if p % 2 == 0:
			print(sum(l) + sum(xorpos))
		else:
			z = sum(xorpos) - min(xorpos)
			if neg > 0:
				x = sum(xorpos) + max(xorneg)
			else:
				x = 0
			print(sum(l) + max(z, x))
	else:
		print(sum(l) + sum(xorpos))
	t = t - 1


def main():
	tstr = input()
	t = int(tstr)
	while t:
		t -= 1
		nstr = input()
		n = int(nstr)
		a = list(map(int, input().split()))
		ans = sum(a)
		kstr = input()
		xstr = input()
		k = int(kstr)
		x = int(xstr)
		d = []
		for ae in a:
			d.append((ae ^ x) - ae)
		d.sort(reverse=True)
		positive = 0
		for i in d:
			if i > 0:
				positive += 1
			else:
				break
		if k != n:
			if positive % 2 == 0 or k % 2 == 1:
				for i in d:
					if i > 0:
						ans += i
					else:
						break
			else:
				prev_positive = 0
				min_negative = 0
				for i in range(n):
					if d[i] > 0:
						ans += d[i]
					else:
						min_negative = d[i]
						prev_positive = d[i - 1]
						break
				if positive == n:
					ans = ans - d[-1]
				elif ans + min_negative > ans - prev_positive:
					ans = ans + min_negative
				else:
					ans = ans - prev_positive
		elif sum(d) >= 0:
			ans += sum(d)
		print(ans)
main()


def max_sum(pos, neg, n, orig_sum, count, k):
	m = 0
	j = 0
	o = 0
	p = 0
	d = len(pos)
	e = len(neg)
	if d > 0:
		o = sum(pos)
		j = min(pos)
	if e > 0:
		p = sum(neg)
		m = max(neg)
	if k == n:
		print(str(max(orig_sum, orig_sum + o + p)))
	elif k % 2 == 1:
		print(max(o + orig_sum, orig_sum))
	elif count % 2 == 0:
		print(o + orig_sum)
	elif count < n:
		print(max(orig_sum + o - j, orig_sum + o + m, orig_sum))
	else:
		print(max(orig_sum + o - j, orig_sum))
t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))
	SUM = sum(l)
	k = int(input())
	x = int(input())
	counter = 0
	pos = []
	neg = []
	for a in l:
		diff = (x ^ a) - a
		if diff > 0:
			counter += 1
			pos.append(diff)
		else:
			neg.append(diff)
	max_sum(pos, neg, n, SUM, counter, k)
	t -= 1


for i in range(int(input())):
	N = int(input())
	arr = [int(i) for i in input().split()]
	K = int(input())
	X = int(input())
	arr1 = []
	arr2 = []
	for i in arr:
		arr1.append(i ^ X)
	for i in range(len(arr)):
		arr2.append(arr1[i] - arr[i])
	arr3 = sorted(arr2, reverse=True)
	if K == N:
		if sum(arr3) > 0:
			x = sum(arr3) + sum(arr)
			print(x)
		else:
			print(sum(arr))
	if K % 2 == 0 and K != N:
		sum1 = 0
		for i in range(0, len(arr) - 1, 2):
			sum2 = 0
			sum2 += arr3[i] + arr3[i + 1]
			if sum2 > 0:
				sum1 += sum2
		print(sum1 + sum(arr))
	if K % 2 != 0 and K != N:
		sum1 = sum(arr)
		for i in arr3:
			if i > 0:
				sum1 += i
		print(sum1)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	k = int(input())
	x = int(input())
	li = []
	for i in l:
		li.append((i ^ x) - i)
	sum_ = sum(l)
	sum_li = sum(li)
	li.sort(reverse=True)
	if n == k:
		if sum_li > 0:
			sum_ += sum_li
	else:
		sum_3 = 0
		if k % 2 == 0:
			for i in range(0, len(li) - 1, 2):
				if li[i] + li[i + 1] > 0:
					sum_3 += li[i] + li[i + 1]
				else:
					break
			sum_ += sum_3
		else:
			sum_3 = 0
			for i in range(len(li)):
				if li[i] > 0:
					sum_3 += li[i]
				else:
					break
			sum_ += sum_3
	print(sum_)


t = int(input())
for i in range(t):
	diff = []
	xed = []
	flag = False
	n = int(input())
	org = list(map(int, input().split()))
	k = int(input())
	x = int(input())
	s_org = sum(org)
	if x == 0:
		print(s_org)
	else:
		for j in org:
			xed.append(j ^ x)
		for j in range(n):
			temp = xed[j] ^ x
			while xed[j] < temp and temp != org[j]:
				xed[j] = temp
				temp = temp ^ x
		if k == n:
			s2 = sum(xed)
			print(max(s_org, s2))
		else:
			nc = 0
			for j in range(n):
				diff.append([xed[j] - org[j], j])
				if xed[j] - org[j] >= 0:
					nc += 1
			if nc % 2 == 0:
				Sum = 0
				for j in range(n):
					if xed[j] > org[j]:
						Sum += xed[j]
					else:
						Sum += org[j]
				print(Sum)
			elif nc % 2 != 0 and k % 2 != 0:
				Sum = 0
				for j in range(n):
					if xed[j] > org[j]:
						Sum += xed[j]
					else:
						Sum += org[j]
				print(Sum)
			elif nc % 2 != 0 and k % 2 == 0:
				mini = abs(diff[j][0])
				for j in range(n):
					if abs(diff[j][0]) < mini:
						mini = abs(diff[j][0])
				Sum = 0
				for j in range(n):
					if xed[j] > org[j]:
						Sum += xed[j]
					else:
						Sum += org[j]
				print(Sum - mini)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	k = int(input())
	x = int(input())
	flipped = []
	increase = []
	count = 0
	for i in range(n):
		flipped.append(a[i] ^ x)
		increase.append([a[i], flipped[i] - a[i]])
		if flipped[i] - a[i] > 0:
			count += 1
	increase.sort(key=lambda x: x[1])
	if k == n:
		print(max(sum(a), sum(flipped)))
	elif k % 2 != 0:
		max_ = []
		for i in range(n):
			if a[i] > flipped[i]:
				max_.append(a[i])
			else:
				max_.append(flipped[i])
		print(sum(max_))
	elif count % 2 == 0:
		max_ = []
		for i in range(n):
			if a[i] > flipped[i]:
				max_.append(a[i])
			else:
				max_.append(flipped[i])
		print(sum(max_))
	else:
		max_ = []
		for i in range(n):
			if a[i] > flipped[i]:
				max_.append(a[i])
			else:
				max_.append(flipped[i])
		min_ = 1000000001
		for i in range(n):
			if abs(a[i] - flipped[i]) < min_:
				min_ = abs(a[i] - flipped[i])
		if min_ == 1000000001:
			print(sum(max_))
		else:
			ans = sum(max_) - min_
			print(ans)


for T in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	K = int(input())
	X = int(input())
	valueIncreases = {}
	valueDecreases = {}
	list_valueIncreases = []
	list_valueDecreases = []
	for a in A:
		d = (a ^ X) - a
		if d > 0:
			valueIncreases[a] = d
			list_valueIncreases.append(a)
		else:
			valueDecreases[a] = d
			list_valueDecreases.append(a)
	s1 = sorted(list_valueIncreases, key=valueIncreases.get)
	s2 = sorted(list_valueDecreases, key=valueDecreases.get)
	sum_valIncreases = 0
	for val in s1:
		sum_valIncreases += valueIncreases[val]
	if len(s1) == 0:
		totalMoney = sum(s2)
	if K == N:
		s2b = s2.copy()
		q = K - len(s1)
		t = 0
		for i in range(q):
			t += valueDecreases[s2b.pop()]
		if t + sum_valIncreases > 0:
			totalMoney = t + sum(s2) + sum(s1) + sum_valIncreases
		else:
			totalMoney = sum(s1) + sum(s2)
	elif K % 2 != 0 or (K % 2 == 0 and len(s1) % 2 == 0):
		totalMoney = sum_valIncreases + sum(s1) + sum(s2)
	else:
		val2 = s1[0]
		if len(s2) == 0:
			totalMoney = sum_valIncreases + sum(s1) + sum(s2) - valueIncreases[val2]
		else:
			val1 = s2[-1]
			if valueDecreases[val1] + valueIncreases[val2] > 0:
				totalMoney = sum_valIncreases + sum(s1) + sum(s2) + valueDecreases[val1]
			else:
				totalMoney = sum_valIncreases + sum(s1) + sum(s2) - valueIncreases[val2]
	print(totalMoney)


import array as money
tcases = int(input())
while tcases != 0:
	noe = int(input())
	money = [int(m) for m in input().split()]
	k = int(input())
	x = int(input())
	totalmoney = 0
	i = 0
	while i < len(money):
		totalmoney += money[i]
		i = i + 1
	if x == 0:
		result = totalmoney
		print(result)
	elif k == noe:
		maxamount = 0
		j = 0
		while j < len(money):
			val = money[j] ^ x
			maxamount += val
			j = j + 1
		if maxamount >= totalmoney:
			result = maxamount
			print(result)
		else:
			result = totalmoney
			print(result)
	else:
		counter = 0
		totalmoney = 0
		bags = []
		for amount in money:
			xorval = amount ^ x
			value = xorval - amount
			if value <= 0:
				value *= -1
			else:
				value = value
			bags.append(value)
			if amount >= xorval:
				totalmoney = totalmoney + amount
			else:
				counter = counter + 1
				totalmoney = totalmoney + xorval
		bags.sort()
		if k % 2 == 0:
			if counter % 2 == 0:
				result = totalmoney
				print(result)
			else:
				mindiff = totalmoney - bags[0]
				result = mindiff
				print(result)
		else:
			result = totalmoney
			print(result)
	tcases = tcases - 1


import math
t = int(input())
for i in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	k = int(input())
	x = int(input())
	ss = sum(a)
	arr = list(map(lambda y: (y ^ x) - y, a))
	arr = sorted(arr, reverse=True)
	count = 0
	for i in arr:
		if i > 0:
			count += 1
	kek = sum(arr)
	if n == k:
		print(ss + max(sum(arr), 0))
		continue
	elif k % 2 == 1:
		pig = 0
	else:
		pig = count % 2
	armod = []
	for i in range(len(arr)):
		armod.append(abs(arr[i]))
	arc = sorted(armod)
	for i in range(pig, len(arr)):
		arc[i] = -arc[i]
	ss += (sum(arr) - sum(arc)) // 2
	count1 = 0
	arr = sorted(arr, reverse=True)
	print(ss)


import sys
T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split(' ')))
	K = int(input())
	X = int(input())
	L = 0
	H = 0
	mini = sys.maxsize
	lowhighs = 0
	lowlows = 0
	highhighs = 0
	highlows = 0
	totalhighs = 0
	for i in A:
		xor = X ^ i
		if xor > i:
			L += 1
			lowhighs += xor
			lowlows += i
			totalhighs += xor
		else:
			H += 1
			highhighs += i
			highlows += xor
			totalhighs += i
		if abs(xor - i) < mini:
			mini = abs(xor - i)
	if N > K:
		if K % 2 == 1:
			print(totalhighs)
		elif L % 2 == 1:
			print(totalhighs - mini)
		else:
			print(totalhighs)
	else:
		a = highhighs + lowlows
		b = lowhighs + highlows
		if a > b:
			print(a)
		else:
			print(b)


for _ in range(int(input())):
	n = int(input())
	ll = list(map(int, input().split()))
	k = int(input())
	x = int(input())
	xor = []
	pos = 0
	neg = 0
	mm = 10 ** 18
	ans = 0
	for i in range(n):
		temp = []
		al = ll[i] ^ x
		al = al - ll[i]
		temp.append(ll[i])
		temp.append(al)
		xor.append(temp)
		if xor[i][1] < 0:
			neg += 1
			ans += ll[i]
		else:
			pos += 1
			ans += ll[i] ^ x
		if abs(ll[i] - (ll[i] ^ x)) < mm:
			mm = abs(ll[i] - (ll[i] ^ x))
	if x == 0 or k == n:
		(summa, summb) = (0, 0)
		for i in range(n):
			summa += xor[i][1] + xor[i][0]
			summb += xor[i][0]
		ans = max(summa, summb)
	elif k % 2 != 0:
		pass
	elif n % 2 != 0:
		if neg % 2 == 0:
			ans -= mm
	elif neg % 2 != 0:
		ans -= mm
	print(ans)


def func(n, arr, k, x):
	a = [0 for i in range(n)]
	for i in range(n):
		a[i] = arr[i] ^ x
	if n == k:
		return max(sum(a), sum(arr))
	elif k % 2 == 1:
		ans = 0
		for i in range(n):
			ans += max(arr[i], a[i])
		return ans
	else:
		count = 0
		ans = 0
		for i in range(n):
			if arr[i] < a[i]:
				count += 1
			ans += max(arr[i], a[i])
		if count % k % 2 == 0:
			return ans
		else:
			mini = ans
			for i in range(n):
				mini = min(abs(arr[i] - a[i]), mini)
			return ans - mini
t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	k = int(input())
	x = int(input())
	print(func(n, arr, k, x))


def sol():
	n = int(input())
	a = list(map(int, input().split()))
	k = int(input())
	x = int(input())
	s = 0
	z = 0
	o = 0
	if n == k:
		temp1 = 0
		temp = 0
		for i in a:
			temp += i
			temp1 += i ^ x
		if temp > temp1:
			print(temp)
		else:
			print(temp1)
		return
	for i in a:
		if (i ^ x) - i > 0:
			z += 1
		else:
			o += 1
	if k % 2 != 0:
		for i in a:
			if (i ^ x) - i >= 0:
				s += i ^ x
			else:
				s += i
	elif z % 2 == 0:
		for i in a:
			if (i ^ x) - i > 0:
				s += i ^ x
			else:
				s += i
	else:
		mindiff = 9999999999
		ind = -1
		for i in range(n):
			temp = abs((a[i] ^ x) - a[i])
			if mindiff > temp:
				mindiff = temp
				ind = i
		for i in range(n):
			temp = (a[i] ^ x) - a[i]
			if i == ind:
				if temp >= 0:
					s += a[i]
				else:
					s += a[i] ^ x
			elif temp <= 0:
				s += a[i]
			else:
				s += a[i] ^ x
	print(s)
t = int(input())
for i in range(t):
	sol()


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	k = int(input())
	x = int(input())
	if n == k:
		sum1 = 0
		sum2 = 0
		for j in range(n):
			sum1 = sum1 + arr[j]
			sum2 = sum2 + (arr[j] ^ x)
		print(max(sum1, sum2))
	else:
		sum1 = 0
		count = 0
		min1 = abs((arr[0] ^ x) - arr[0])
		for j in range(n):
			r = arr[j] ^ x
			if r > arr[j]:
				sum1 = sum1 + r
				count += 1
			else:
				sum1 = sum1 + arr[j]
			z = abs(r - arr[j])
			if z < min1:
				min1 = z
		if count % 2 != 0:
			if k % 2 == 0:
				print(sum1 - min1)
			else:
				print(sum1)
		else:
			print(sum1)


for q in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	k = int(input())
	x = int(input())
	sumyet = 0
	posi = 0
	xor = []
	for i in range(n):
		xor.append(arr[i] ^ x)
	if k == n:
		if sum(xor) > sum(arr):
			print(sum(xor))
		else:
			print(sum(arr))
	else:
		for i in range(n):
			sumyet += max(xor[i], arr[i])
			if xor[i] > arr[i]:
				posi += 1
			arr[i] = abs(arr[i] - xor[i])
		if not k & 1 and posi & 1:
			sumyet -= min(arr)
		print(sumyet)


def myXOR(x, y):
	return (x | y) & (~x | ~y)
t = int(input())
for ij in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	k = int(input())
	xd = int(input())
	high = []
	low = []
	for i in range(len(l)):
		if myXOR(l[i], xd) >= l[i]:
			low.append(l[i])
		else:
			high.append(l[i])
	d = 0
	x = 0
	y = 0
	if k % 2 == 0:
		d = 2
		x = k // 2 - 1
		y = x + 2
	else:
		d = 1
		x = k // 2
		y = x + 1
	a = len(low)
	b = len(high)
	b += a - a % k
	a = a % k
	while b >= y and a < k:
		b -= d
		a += d
	b += a - a % k
	a = a % k
	gain = []
	for i in range(len(low)):
		t = myXOR(low[i], xd) - low[i]
		gain.append(t)
	for i in range(len(high)):
		t = high[i] - myXOR(high[i], xd)
		gain.append(t)
	gain.sort()
	i = a
	s = 0
	while i < len(gain):
		s += gain[i]
		i += 1
	sm = 0
	if n == k:
		for i in low:
			sm += i
		for i in high:
			sm += i
		sm1 = 0
		for i in high:
			sm1 += myXOR(i, xd)
		for i in low:
			sm1 += myXOR(i, xd)
		print(max(sm, sm1))
	elif k % 2 != 0:
		sm = 0
		for i in low:
			sm += myXOR(i, xd)
		for i in high:
			sm += i
		print(sm)
	elif len(low) % 2 == 0:
		sm = 0
		for i in low:
			sm += myXOR(i, xd)
		for i in high:
			sm += i
		print(sm)
	else:
		sm = 0
		for i in low:
			sm += myXOR(i, xd)
		for i in high:
			sm += i
		print(sm - gain[0])


def optimal_operation_sum(N, A, K, X):
	xor = [X ^ y for y in A]
	diff = [xor[i] - A[i] for i in range(N)]
	improvment_cnt = sum((y > 0 for y in diff))
	A_sum = sum(A)
	if K == N:
		return max(A_sum, A_sum + sum(diff))
	pos_improvement = [y for y in diff if y > 0]
	non_improvement = [y for y in diff if y <= 0]
	max_improvement = sum(pos_improvement)
	if improvment_cnt % 2 == 0 or K % 2 == 1:
		return A_sum + max_improvement
	else:
		under = over = A_sum
		if pos_improvement:
			under = A_sum + max_improvement - min(pos_improvement)
		if non_improvement:
			over = A_sum + max_improvement + max(non_improvement)
		return max(under, over)
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	K = int(input())
	X = int(input())
	print(optimal_operation_sum(N, A, K, X))


t = int(input())
mod = 10 ** 9 + 7
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	k = int(input())
	x = int(input())
	profits = [(i ^ x) - i for i in a]
	profits.sort()
	profits = profits[::-1]
	pr = 0
	pos = 0
	for i in range(n):
		if profits[i] >= 0:
			pos = i
		else:
			break
	pos += 1
	if n == k:
		if sum(profits) > 0:
			pr += sum(profits)
	elif pos % 2 == 0:
		for i in profits:
			if i > 0:
				pr += i
	elif k % 2:
		for i in profits:
			if i > 0:
				pr += i
	else:
		for i in range(n // 2):
			if profits[2 * i] + profits[2 * i + 1] > 0:
				pr += profits[2 * i] + profits[2 * i + 1]
	print(sum(a) + pr)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split(' ')))
	k = int(input())
	x = int(input())
	s = sum(l)
	ldiff = []
	if n == k:
		xorarr = []
		for i in range(0, len(l)):
			xorarr.append(l[i] ^ x)
		sum1 = sum(xorarr)
		if sum1 > s:
			print(sum1)
		else:
			print(s)
	else:
		count = 0
		for i in l:
			p = i ^ x
			if p - i > 0:
				s = s + (p - i)
				count += 1
			ldiff.append(abs(p - i))
		if k % 2 == 0 and count % 2 != 0:
			print(s - min(ldiff))
		else:
			print(s)


from math import inf
t = int(input())
for w in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	k = int(input())
	x = int(input())
	barr = []
	for i in arr:
		barr.append(i ^ x)
	if k == n:
		print(max(sum(arr), sum(barr)))
	elif k % 2 == 1:
		for i in range(n):
			barr[i] = max(barr[i], arr[i])
		print(sum(barr))
	else:
		count = 0
		for i in range(n):
			if arr[i] < barr[i]:
				count += 1
		count = count % k
		if count % 2 == 0:
			for i in range(n):
				barr[i] = max(barr[i], arr[i])
			print(sum(barr))
		else:
			flag = 0
			diff = inf
			for i in range(n):
				diff = min(diff, abs(arr[i] - barr[i]))
			for i in range(n):
				barr[i] = max(barr[i], arr[i])
			print(sum(barr) - diff)


for jqw in range(int(input())):
	n = int(input())
	a = [int(yu) for yu in input().split(' ')]
	k = int(input())
	x = int(input())
	l = []
	s = sum(a)
	for j in a:
		l.append((j ^ x) - j)
	l.sort(reverse=True)
	if k == n:
		s = max(s, s + sum(l))
		print(s)
		continue
	if k % 2 == 0:
		for j in range(0, len(l), 2):
			if j + 1 < len(l):
				ans = l[j] + l[j + 1]
				if ans > 0:
					s = s + ans
	else:
		for j in l:
			if j > 0:
				s = s + j
			else:
				break
	print(s)


t = int(input())

class money:

	def __init__(self, original, xor):
		self.original = original
		self.xor = xor
for iii in range(t):
	n = int(input())
	a = input()
	a = list(map(int, a.split(' ')))
	k = int(input())
	x = int(input())
	if n == k:
		summ = 0
		summ_xor = 0
		for i in range(len(a)):
			summ += a[i]
			summ_xor += a[i] ^ x
		print(max(summ, summ_xor))
		continue
	xor_list = []
	for i in range(len(a)):
		xor_list.append(money(a[i], a[i] ^ x))
	summ = 0
	number_inc = 0
	for i in range(len(a)):
		if xor_list[i].original > xor_list[i].xor:
			summ += xor_list[i].original
		else:
			summ += xor_list[i].xor
			number_inc += 1
	if k % 2 == 1:
		print(summ)
		continue
	elif number_inc % 2 == 0 and k % 2 == 0:
		print(summ)
		continue
	diff = []
	for i in range(len(a)):
		diff.append(abs(xor_list[i].original - xor_list[i].xor))
	min_difference = min(diff)
	print(summ - min_difference)


import numpy as np
t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split()))
	k = int(input())
	x = int(input())
	l = []
	suma = suml = z = 0
	possum = []
	negsum = []
	for i in range(0, n):
		l.append(np.bitwise_xor(a[i], x))
		suma += a[i]
		suml += l[i]
		if l[i] > a[i]:
			z += 1
			possum.append(l[i] - a[i])
		else:
			negsum.append(l[i] - a[i])
	if n == k:
		print(max(suma, suml))
	elif z % 2 == 0 or (z - k) % 2 == 0:
		print(suma + sum(possum))
	elif z != n:
		print(max(suma + sum(possum) - min(possum), suma + sum(possum) + max(negsum)))
	else:
		print(suma + sum(possum) - min(possum))
	t -= 1


import math
t = int(input())
for T in range(t):
	n = int(input())
	s = input()
	a = []
	k = int(input())
	x = int(input())
	a = s.split(' ')
	for i in range(n):
		a[i] = int(a[i])
	sum_f = sum(a)
	(xor, diff) = ([], [])
	(pos_diff, neg_diff) = ([], [])
	for i in range(n):
		xor.append(a[i] ^ x)
		diff.append(xor[i] - a[i])
		if diff[i] >= 0:
			pos_diff.append(diff[i])
		else:
			neg_diff.append(diff[i])
	if x == 0:
		print(sum_f)
	elif k == n:
		if sum(pos_diff) > -1 * sum(neg_diff):
			print(sum_f + sum(pos_diff) + sum(neg_diff))
		else:
			print(sum_f)
	elif k % 2 == 0 and len(pos_diff) % 2 != 0:
		if len(pos_diff) == 0:
			print(sum_f)
		elif len(neg_diff) == 0:
			print(sum_f + sum(pos_diff) - min(pos_diff))
		else:
			print(sum_f + sum(pos_diff) - min(min(pos_diff), -1 * max(neg_diff)))
	else:
		print(sum_f + sum(pos_diff))


def sortSecond(val):
	return val[0]
t = int(input())
for i in range(t):
	n = int(input())
	l = input().split()
	k = int(input())
	x = int(input())
	a = []
	ma = 0
	suma = 0
	sumb = 0
	for j in range(len(l)):
		l[j] = int(l[j])
		change = (l[j] ^ x) - l[j]
		a.append((change, l[j]))
	a.sort(key=sortSecond, reverse=True)
	if k % 2 == 0:
		sa = 0
		for j in range(n):
			sa = sa + a[j][0]
			if j % 2 == 1:
				ma = max(ma, sa)
			suma = suma + a[j][1]
			sumb = sumb + a[j][0]
	else:
		sa = 0
		for j in range(n):
			sa = sa + a[j][0]
			ma = max(ma, sa)
			suma = suma + a[j][1]
			sumb = sumb + a[j][0]
	if k == n:
		print(max(suma + sumb, suma))
	else:
		print(suma + ma)


def radix_sort(alist, base=10):
	if alist == []:
		return

	def key_factory(digit, base):

		def key(alist, index):
			return alist[index] // base ** digit % base
		return key
	largest = max(alist)
	exp = 0
	while base ** exp <= largest:
		alist = counting_sort(alist, base - 1, key_factory(exp, base))
		exp = exp + 1
	return alist

def counting_sort(alist, largest, key):
	c = [0] * (largest + 1)
	for i in range(len(alist)):
		c[key(alist, i)] = c[key(alist, i)] + 1
	c[0] = c[0] - 1
	for i in range(1, largest + 1):
		c[i] = c[i] + c[i - 1]
	result = [None] * len(alist)
	for i in range(len(alist) - 1, -1, -1):
		result[c[key(alist, i)]] = alist[i]
		c[key(alist, i)] = c[key(alist, i)] - 1
	return result
T = int(input())
for i in range(T):
	N = int(input())
	L1 = list(map(int, input().split()))
	K = int(input())
	X = int(input())
	error = 0.0
	err = 0
	a = 0
	for i in range(N):
		a = a + L1[i]
	b = 0
	L2 = []
	res = []
	for i in range(N):
		L2.append(L1[i] ^ X)
		b = b + L2[i]
		res.append(L2[i] - L1[i])
	res.sort(reverse=True)
	req = 0
	c = 0
	d = 0
	if N == K:
		a = max(a, b)
	elif K % 2 == 1:
		for i in range(N):
			d = d + res[i]
			req = max(req, d)
	elif 0 < K % 2 < 1:
		error = error + 1
	else:
		for i in range(N):
			c = c + res[i]
			if i % 2 == 1:
				req = max(req, c)
	for i in range(req % 2):
		err = err + 1
	print(a + req)


test = int(input())
for _ in range(test):
	N = int(input())
	A = [int(x) for x in input().split()]
	K = int(input())
	X = int(input())
	diffs = []
	positives = []
	pos_count = 0
	for i in A:
		diffs.append((i ^ X) - i)
	diffs.sort(reverse=True)
	for i in range(N):
		if diffs[i] > 0:
			pos_count += 1
	sum_all = sum(A)
	sum_positive = sum(diffs[:pos_count])
	if N == K:
		ans = max(sum_all, sum_all + sum(diffs))
	elif pos_count % 2 == 0:
		ans = sum_all + sum_positive
	elif pos_count == N:
		if K % 2 == 0:
			ans = sum_all + sum_positive - diffs[N - 1]
		else:
			ans = sum_all + sum_positive
	elif K % 2 == 0:
		ans1 = sum_all + sum_positive - diffs[pos_count - 1]
		ans2 = sum_all + sum_positive + diffs[pos_count]
		ans = max(ans1, ans2)
	else:
		ans = sum_all + sum_positive
	print(ans)


t = int(input())
for c in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	k = int(input())
	x = int(input())
	g = []
	l = []
	for i in range(n):
		if (arr[i] ^ x) - arr[i] > 0:
			g.append((arr[i] ^ x) - arr[i])
		else:
			l.append((arr[i] ^ x) - arr[i])
	p = len(g)
	neg = len(l)
	ans = sum(arr)
	if x == 0:
		print(ans)
	elif k == p and x != 0:
		ans += sum(g)
		print(ans)
	elif k == n:
		if k == p:
			ans += sum(g)
			print(ans)
		elif k != p:
			t = ans + sum(g) + sum(l)
			if t > ans:
				ans = t
			print(ans)
	else:
		ans += sum(g)
		if p % 2 == 1 and k % 2 == 0:
			if neg > 0:
				ans = max(ans + max(l), ans - min(g))
			else:
				ans -= min(g)
		print(ans)


t = int(input())
while t > 0:
	n = int(input())
	A = list(map(int, input().split()))
	k = int(input())
	x = int(input())
	mini = abs(A[0] - (A[0] ^ x))
	maxsum = 0
	sumkn = 0
	count = 0
	for i in range(len(A)):
		maxsum = maxsum + max(A[i], A[i] ^ x)
		sumkn += A[i] ^ x
		if A[i] ^ x > A[i]:
			count += 1
		mini = min(mini, abs(A[i] - (A[i] ^ x)))
	answer = maxsum
	if k != n and count % 2 == 1 and (k % 2 == 0):
		answer = answer - mini
	if k == n:
		answer = max(sumkn, sum(A))
	print(answer)
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	k = int(input())
	x = int(input())
	if x == 0:
		print(sum(a))
	elif n == k:
		s1 = sum(a)
		b = [h ^ x for h in a]
		s2 = sum(b)
		print(max(s1, s2))
	else:
		p = []
		m = []
		for y in a:
			d = (y ^ x) - y
			if d >= 0:
				p.append(d)
			else:
				m.append(d)
		m1 = len(m)
		p1 = len(p)
		s = 0
		if p1 > 0:
			if p1 % 2 == 0 or k % 2 == 1:
				s += sum(p)
			else:
				t1 = min(p)
				s += sum(p) - t1
				if m1 > 0:
					t2 = max(m)
					if t1 + t2 >= 0:
						s += t2 + t1
		print(sum(a) + s)


t = int(input())
for _ in range(t):
	n = int(input())
	a = []
	a = list(map(int, input().split()))
	k = int(input())
	x = int(input())
	b = [(a[i] ^ x) - a[i] for i in range(n)]
	if k == len(a):
		print(max(sum(a), sum(a) + sum(b)))
	elif k % 2 == 0:
		k = 2
		b.sort()
		count = 0
		ans = 0
		i = len(b) - 1
		while i >= 0 and b[i] > 0:
			count += 1
			ans += b[i]
			store = i
			i -= 1
		if count == len(b) and count % 2 == 0:
			print(sum(a) + sum(b))
		elif count == len(b) and count % 2 == 1:
			print(sum(a) + sum(b) - b[0])
		elif count % 2 == 0:
			print(sum(a) + ans)
		else:
			ans1 = 0
			for i in range(n - 1, store, -1):
				ans1 += b[i]
			print(sum(a) + max(ans1, ans1 + b[store] + b[store - 1]))
	elif k % 2 == 1:
		k = 1
		ans = 0
		for i in range(n):
			if b[i] > 0:
				ans += b[i]
		print(sum(a) + ans)


T = int(input())
while T > 0:
	T -= 1
	N = int(input())
	L = list(map(int, input().split()))
	SS = sum(L)
	K = int(input())
	X = int(input())
	Q = []
	SumQ = 0
	NooS = 0
	for i in L:
		KK = X ^ i
		Q.append(KK)
		SumQ += KK
		if KK > i:
			NooS += 1
	MSum = 0
	for i in range(0, N):
		if Q[i] > L[i]:
			MSum += Q[i]
		else:
			MSum += L[i]
	Diff = 10 ** 9 + 1
	for i in range(0, N):
		GG = abs(Q[i] - L[i])
		if GG < Diff:
			Diff = GG
	if K != N:
		if K % 2 != 0:
			print(MSum)
		elif NooS % 2 != 0:
			print(MSum - Diff)
		else:
			print(MSum)
	elif SumQ > SS:
		print(SumQ)
	else:
		print(SS)


t = int(input())
for asd in range(t):
	n = int(input())
	ar = list(map(int, input().split()))
	k = int(input())
	x = int(input())
	pos = []
	neg = []
	for i in range(n):
		ch = ar[i] ^ x
		if ch > ar[i]:
			pos.append((ch - ar[i], ar[i]))
		else:
			neg.append((ar[i] - ch, ar[i]))
	if k == 0:
		sum = 0
		for i in range(n):
			sum += ar[i]
		print(sum)
		continue
	if k == n:
		sum = 0
		sum1 = 0
		sum2 = 0
		for i in range(n):
			sum1 += ar[i]
			sum2 += ar[i] ^ x
		sum = max(sum1, sum2)
		print(sum)
		continue
	if k % 2 == 1:
		sum = 0
		for i in range(n):
			sum += max(ar[i], ar[i] ^ x)
		print(sum)
		continue
	if k % 2 == 0:
		sum = 0
		if len(pos) == n:
			pos.sort()
			i = len(pos) - 1
			while i - 1 >= 0:
				sum += pos[i][1] ^ x
				sum += pos[i - 1][1] ^ x
				i -= 2
			if i >= 0:
				sum += pos[i][1]
		elif len(pos) % 2 == 0:
			for i in range(len(pos)):
				sum += pos[i][1] ^ x
			for i in range(len(neg)):
				sum += neg[i][1]
		elif len(pos) % 2 == 1:
			pos.sort()
			neg.sort()
			if pos[0][0] >= neg[0][0]:
				for i in range(len(pos)):
					sum += pos[i][1] ^ x
				sum += neg[0][1] ^ x
				for i in range(1, len(neg)):
					sum += neg[i][1]
			else:
				sum = pos[0][1]
				for i in range(1, len(pos)):
					sum += pos[i][1] ^ x
				for i in range(len(neg)):
					sum += neg[i][1]
		print(sum)
		continue


for t in range(int(input())):
	n = int(input())
	list1 = list(map(int, input().split()))
	k = int(input())
	x = int(input())
	list2 = [i ^ x for i in list1]
	list3 = [j - i for (i, j) in zip(list1, list2)]
	if n == 1:
		print(max(list1[0], list2[0]))
		continue
	if k == n:
		print(max(sum(list1), sum(list2)))
		continue
	pos_min = max(list3)
	neg_max = min(list3)
	sum1 = 0
	count1 = 0
	for i in range(n):
		if list3[i] > 0:
			sum1 = sum1 + list2[i]
			count1 = count1 + 1
			if list3[i] < pos_min:
				pos_min = list3[i]
		else:
			sum1 = sum1 + list1[i]
			if list3[i] > neg_max:
				neg_max = list3[i]
	if count1 % 2 == 0 or k % 2 == 1 or count1 % k == 0:
		print(sum1)
	elif count1 == n:
		print(sum1 - pos_min)
	else:
		print(max(sum1 + neg_max, sum1 - pos_min))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().rstrip().split()))
	k = int(input())
	x = int(input())
	xo = []
	for x1 in l:
		xo.append(x1 ^ x)
	diff = []
	for x in range(n):
		diff.append(xo[x] - l[x])
	z = list(zip(diff, xo, l))
	cp = 0
	for x in diff:
		if x > 0:
			cp += 1
	if k == n:
		print(max(sum(l), sum(xo)))
	elif k % 2 != 0:
		s = 0
		for x in z:
			if x[0] > 0:
				s += x[1]
			else:
				s += x[2]
		print(s)
	elif k % 2 == 0:
		if cp % 2 == 0:
			s = 0
			for x in z:
				if x[0] > 0:
					s += x[1]
				else:
					s += x[2]
			print(s)
		elif cp == n:
			q1 = cp - 1
			z.sort(key=lambda x: x[0], reverse=True)
			s1 = 0
			for x in range(n):
				if x < q1:
					s1 += z[x][1]
				else:
					s1 += z[x][2]
			print(s1)
		else:
			q1 = cp - 1
			q2 = cp + 1
			z.sort(key=lambda x: x[0], reverse=True)
			s1 = 0
			s2 = 0
			for x in range(n):
				if x < q1:
					s1 += z[x][1]
				else:
					s1 += z[x][2]
				if x < q2:
					s2 += z[x][1]
				else:
					s2 += z[x][2]
			print(max(s1, s2))


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	k = int(input())
	x = int(input())
	r = [0] * n
	for i in range(n):
		r[i] = l[i] ^ x
	sum1 = sum(l)
	p = [0] * n
	for i in range(n):
		p[i] = r[i] - l[i]
	x = sorted(p, reverse=True)
	sum2 = sum1
	count = 0
	if k == n:
		sum2 = sum1 + sum(x)
		if sum2 > sum1:
			print(sum2)
		else:
			print(sum1)
		continue
	if k % 2 == 0:
		i = 0
		while i < n - 1:
			sum2 += x[i] + x[i + 1]
			i += 2
			if sum2 > sum1:
				sum1 = sum2
			else:
				break
	if k % 2 == 1:
		for i in range(n):
			sum2 += x[i]
			if sum2 > sum1:
				sum1 = sum2
			else:
				break
	print(sum1)