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

Chef is really interested in the XOR operation. He wants to take a sequence $A_{0}, A_{1}, \ldots, A_{N-1}$ and for each $i$ from $0$ to $K-1$ inclusive (in this order, one by one), perform the following operation:
Let's denote $a = A_{i\%N}$ and $b = A_{N-(i\%N)-1}$ before this operation.
Change $A_{i\%N}$ to $a \oplus b$, i.e. $a$ XOR $b$.

Since Chef is busy, he asked you to find the final sequence he should get after performing these operations.

------  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 $K$.
The second line contains $N$ space-separated integers $A_{0}, A_{1}, \ldots, A_{N-1}$.

------  Output ------
For each test case, print a single line containing $N$ space-separated integers ― the elements of the final sequence.

------  Constraints ------
$1 ≤ T ≤ 70$
$1 ≤ N ≤ 10^{4}$
$1 ≤ K ≤ 10^{12}$
$1 ≤ A_{i} ≤ 10^{7}$ for each valid $i$

------  Subtasks ------
Subtask #1 (30 points): $1 ≤ K ≤ 10^{6}$

Subtask #2 (70 points): original constraints

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

2 2

1 2
----- Sample Output 1 ------ 
3 1

Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Data structures

Mathematics
Skill types: Bit manipulation

Data structures

Starter code:

Solutions:
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	if k > n * 3:
		k = k % (n * 3) + n * 3
	for i in range(k):
		a = l[i % n]
		b = l[n - i % n - 1]
		l[i % n] = a ^ b
	print(*l)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if k > n * 3:
		k = k % (n * 3) + n * 3
	for i in range(k):
		x = i % n
		y = a[n - x - 1]
		p = a[x]
		a[x] = p ^ y
	print(*a)


t = int(input())
for i in range(t):
	(N, k) = map(int, input().split())
	c = list(map(int, input().split()))
	if k > N * 3:
		k = k % (N * 3) + N * 3
	for i in range(k):
		a = c[i % N]
		b = c[N - i % N - 1]
		c[i % N] = a ^ b
	for i in c:
		print(i, end=' ')


n = int(input())
for i in range(n):
	(m, k) = map(int, input().split())
	l = list(map(int, input().split()))
	if k >= m * 3:
		k = m * 3 + k % (m * 3)
	for j in range(k):
		r = j % m
		a = l[r]
		b = l[m - r - 1]
		l[r] = a ^ b
	print(*l)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if k >= n and n % 2 == 1:
		a[n // 2] = 0
	x = k // n % 3
	for j in range(x):
		for i in range(n):
			b = a[i]
			c = a[n - i - 1]
			a[i] = b ^ c
	y = k % n
	for i in range(y):
		b = a[i]
		c = a[n - i - 1]
		a[i] = b ^ c
	print(*a)


t = int(input())
for _ in range(t):
	(N, K) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	if K > N * 3:
		K = K % (N * 3) + N * 3
	for i in range(K):
		x = a[i % N]
		y = a[N - i % N - 1]
		a[i % N] = x ^ y
	print(*a)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if k > n * 3:
		k = k % (n * 3) + n * 3
	for i in range(k):
		x = i % n
		p = a[x]
		b = a[n - x - 1]
		a[x] = p ^ b
	for i in a:
		print(i, end=' ')


def sol(n, k, arr):
	if k >= n * 3:
		k = n * 3 + k % (n * 3)
	for i in range(k):
		arr[i % n] = arr[i % n] ^ arr[n - i % n - 1]
	return arr
y = int(input())
for i in range(y):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	print(*sol(n, k, arr))


N = int(input())
for i in range(N):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	if k >= n * 3:
		k = n * 3 + k % (n * 3)
	for i in range(0, k):
		r = i % n
		a = l[r]
		b = l[n - r - 1]
		l[r] = a ^ b
	print(*l)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	a = list(map(int, input().split()))
	if K >= N and N % 2 == 1:
		a[N // 2] = 0
	x = K // N % 3
	for j in range(x):
		for i in range(N):
			b = a[i]
			c = a[N - i - 1]
			a[i] = b ^ c
	y = K % N
	for i in range(y):
		b = a[i]
		c = a[N - i - 1]
		a[i] = b ^ c
	print(*a)


t = int(input())
while t > 0:
	(n, k) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	i = 0
	if k >= n * 3:
		k = n * 3 + k % (n * 3)
	while i < k:
		a = l[i % n]
		b = l[n - i % n - 1]
		l[i % n] = a ^ b
		i += 1
	for i in l:
		print(i, ' ', end='')
	t = t - 1


z = int(input())
for j in range(z):
	(N, k) = map(int, input().split())
	c = list(map(int, input().split()))
	if k > N * 3:
		k = k % (N * 3) + N * 3
	for i in range(k):
		a = c[i % N]
		b = c[N - i % N - 1]
		c[i % N] = a ^ b
	print(*c)


t = int(input())
for i in range(0, t):
	(n, k) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	if k > n and n % 2 == 1:
		l[n // 2] = 0
	num = k // n % 3
	for j in range(0, num):
		for x in range(0, n):
			a = l[x % n]
			b = l[n - x % n - 1]
			l[x % n] = a ^ b
	for j in range(0, k % n):
		a = l[j % n]
		b = l[n - j % n - 1]
		l[j % n] = a ^ b
	print(*l, sep=' ')


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	ar = list(map(int, input().split()))
	b = n * 3
	if k > b:
		k = k % b + b
	for i in range(0, k):
		ar[i % n] = ar[i % n] ^ ar[n - i % n - 1]
	print(*ar)


n = int(input())
for i in range(n):
	(N, K) = map(int, input().split())
	lst = list(map(int, input().split()))
	a = lst[0]
	if K > N * 3:
		K = K % (N * 3) + N * 3
	for i in range(K):
		a = lst[i % N]
		b = lst[N - i % N - 1]
		out = a ^ b
		a = out
		lst[i % N] = out
	print(*lst)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	r = []
	if k > n * 3:
		k = k % (n * 3) + n * 3
	for i in range(k):
		x = i % n
		p = a[x]
		q = a[n - x - 1]
		a[x] = p ^ q
	for i in a:
		print(i, end=' ')