Consider a zero-indexed matrix with $m$ rows and $n$ columns, where each row is filled gradually. Given the first row of the matrix, you can generate the elements in the subsequent rows using the following formula:

$a_{i,j}=a_{i-1,j}\oplus a_{i-1,j+1}\text{}\forall j:0\leq j\leq n-2$
$a_{i,n-1}=a_{i-1,n-1}\oplus a_{i-1,0}$

Each row is generated one by one, from the second row through the last row. Given the first row of the matrix, find and print the elements of the last row as a single line of space-separated integers.

Note: The $\theta$ operator denotes bitwise XOR.

Input Format

The first line contains two space-separated integers denoting the respective values of $n$ (the number of columns in the matrix) and $m$ (the number of rows in the matrix). 

The second line contains $n$ space-separated integers denoting the respective values of the elements in the matrix's first row.

Constraints

$1\leq n\leq10^5$
$1\leq m\leq10^{18}$
$0\leq a_{i,j}\leq10^9$

Output Format

Print $n$ space-separated integers denoting the respective values of the elements in the last row of the matrix.

Sample Input 0
4 2
6 7 1 3

Sample Output 0
1 6 2 5

Explanation 0

We use the formula given above to calculate the $n=4$ values in the last row of the matrix:

$a_{1,0}=a_{0,0}\oplus a_{0,1}=6\oplus7=1$  
$a_{1,1}=a_{0,1}\oplus a_{0,2}=7\oplus1=6$  
$a_{1,2}=a_{0,2}\oplus a_{0,3}=1\oplus3=2$  
$a_{1,3}=a_{0,3}\oplus a_{0,0}=3\oplus6=5$  

We then print each value (in order) as a single line of space-separated integers.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Bit manipulation


Solutions:
(n, m) = map(int, input().split())
ar = tuple(map(int, input().split()))
i = 1
m -= 1
while m:
	if m & 1:
		j = i % n
		ar = tuple((ar[pos] ^ ar[(pos + j) % n] for pos in range(n)))
	m >>= 1
	i <<= 1
print(*ar)


import math

def foo(a, n, m):
	if m == 1:
		return
	x = int(math.floor(math.log(m, 2)))
	if m == 2 ** x:
		x -= 1
	y = m - 2 ** x
	k = pow(2, x, n)
	b = [0] * n
	for i in range(n):
		b[i] = a[i] ^ a[(i + k) % n]
	for i in range(n):
		a[i] = b[i]
	foo(a, n, y)
(n, m) = list(map(int, input().split()))
a = list(map(int, input().split()))
foo(a, n, m)
print(' '.join([str(x) for x in a]))


(n, m) = map(int, input().strip().split())
A = [int(i) for i in input().strip().split()]
k = m - 1
(P, p) = ([], 1)
while k:
	P.append(k & 1)
	p <<= 1
	k >>= 1
while P:
	p >>= 1
	k = P.pop()
	if k:
		B = [A[i] ^ A[(i + p) % n] for i in range(n)]
		A = B
print(' '.join(map(str, A)))


import sys, math

def solve(N, M, row):
	if M == 1:
		return ' '.join([str(i) for i in row])
	largest_log = math.floor(math.log(M, 2))
	offset = 2 ** (largest_log - 1)
	new_row = []
	for i in range(N):
		new_row += [row[i] ^ row[(i + offset) % N]]
	return solve(N, M - offset, new_row)
(N, M) = [int(i) for i in input().strip().split()]
row = [int(i) for i in input().strip().split()]
print(solve(N, M, row))


from array import array

def print_output(line):
	out = ''
	for val in line:
		out += ' ' + str(val)
	print(out.strip())

def advance(line, iterations):
	line_length = len(line)
	for a in map(lambda x: 1 << 63 - x, range(0, 64)):
		if a <= iterations:
			line = array('L', map(lambda x: line[x] ^ line[(x + a) % line_length], range(0, line_length)))
			iterations -= a
	return line
[width, depth] = list(map(int, input().split()))
top_line = array('L', map(int, input().split()))
print_output(advance(top_line, depth - 1))


from math import log, pow
(n, m) = map(int, input().split(' '))
frow = list(map(int, input().split(' ')))
while m > 1:
	jump = int(pow(2, int(log(m, 2))))
	modjump = jump % (n * 2)
	if modjump <= n:
		xorrange = [0, modjump]
	else:
		xorrange = [modjump - n, n]
	xored = 0
	for i in range(xorrange[0], xorrange[1]):
		xored = xored ^ frow[i]
	jumprow = [xored]
	for i in range(1, n):
		xored = jumprow[i - 1]
		xored = xored ^ frow[(xorrange[0] + i - 1) % n]
		xored = xored ^ frow[(xorrange[1] + i - 1) % n]
		jumprow.append(xored)
	m = m - jump + 1
	frow = jumprow
print(' '.join(map(str, frow)))


def nextr(l, step=1):
	n = len(l)
	nextl = []
	for i in range(n):
		nextl.append(l[i] ^ l[(i + step) % n])
	return nextl

def get_row(l, n):
	i = 1
	while n:
		if n & 1:
			l = nextr(l, i)
		n >>= 1
		i <<= 1
	return l
(columns, rows) = (int(x) for x in input().split(' '))
l = [int(x) for x in input().split(' ')]
print(' '.join((str(x) for x in get_row(l, rows - 1))))


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = [0] * len(a)
strm = bin(m - 1)[2:]
lstrm = len(strm)
compt = 0
for s in strm:
	compt += 1
	if int(s) % 2:
		for j in range(n):
			b[j] = a[j] ^ a[(j + 2 ** (lstrm - compt)) % n]
		(a, b) = (b, a)
print(*a)


(n, m) = map(int, input().split())
ar = [int(i) for i in input().split()]
m -= 1
ans = [i for i in ar]
while 0 != m:
	i = 0
	while 2 ** i < m:
		i += 1
	closest_2nd = i - 1
	if closest_2nd == -1:
		closest_2nd = 0
	temp = [0 for i in range(n)]
	for i in range(n):
		temp[i] = ans[i] ^ ans[(i + 2 ** closest_2nd) % n]
	for i in range(n):
		ans[i] = temp[i]
	m = m - 2 ** closest_2nd
final = ''
for i in range(n):
	final += str(ans[i]) + ' '
print(final.strip())


(n, m) = [int(s) for s in input().split()]
a = [int(s) for s in input().split()]
while 1 < m:
	m2 = 1
	while 2 * m2 < m:
		m2 *= 2
	m -= m2
	m2 %= n
	b = list(a)
	for j in range(n):
		a[j] ^= b[(j + m2) % n]
print(' '.join((str(x) for x in a)))


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
m -= 1
t = 1
while m:
	if t & m == 0:
		t *= 2
		continue
	b = []
	j = t % n
	for i in range(n):
		b.append(a[i] ^ a[j])
		j += 1
		if j == n:
			j = 0
	a = b
	m -= t
	t *= 2
print(*a)


from operator import xor

def fast_xor_row(row, column):
	partial_matrix = [row]
	base2 = 1
	c = column
	while c > 0:
		if c % 2 == 1:
			t = []
			for i in range(len(row)):
				t.append(xor(partial_matrix[-1][i], partial_matrix[-1][(i + base2) % len(row)]))
			partial_matrix.append(t)
		base2 *= 2
		c //= 2
	return partial_matrix[-1]
(_, depth) = [int(i) for i in input().split()]
row = [int(i) for i in input().split()]
out = fast_xor_row(row, depth - 1)
print(' '.join([str(i) for i in out]))


(n, m) = map(int, input().strip().split())
A = [int(i) for i in input().strip().split()]
m -= 1
(Bin, val) = ([], 1)
while m:
	Bin.append(m & 1)
	val <<= 1
	m >>= 1
while Bin:
	val >>= 1
	if Bin.pop():
		B = [A[i] ^ A[(i + val) % n] for i in range(n)]
		A = B
print(' '.join(map(str, A)))


(n, m) = map(int, input().split())
ar = tuple(map(int, input().split()))
i = 1
m -= 1
while m:
	if m & 1:
		j = i % n
		ar = tuple((ar[pos] ^ ar[(pos + j) % n] for pos in range(n)))
	m >>= 1
	i <<= 1
print(*ar)


import math

def max_power(n):
	mask = 2 ** 60
	while mask > 0:
		if mask & n:
			return mask
		mask >>= 1
	else:
		raise ValueError('Zero input')
(c, r) = [int(x) for x in input().strip().split()]
values = [int(x) for x in input().strip().split()]
if r == 1:
	for x in values:
		print(x, end=' ')
	print()
elif c == 1:
	print(0)
else:
	while r > 2:
		k = max_power(r - 1)
		r -= k
		values = [values[i] ^ values[int((i + k) % c)] for i in range(len(values))]
	if r == 2:
		values = [values[i] ^ values[int((i + 1) % c)] for i in range(len(values))]
	for k in values:
		print(k, end=' ')
	print()


from math import log, pow
(n, m) = map(int, input().split(' '))
frow = list(map(int, input().split(' ')))
while m > 1:
	jump = int(pow(2, int(log(m, 2))))
	modjump = jump % (n * 2)
	if modjump <= n:
		xorrange = [0, modjump]
	else:
		xorrange = [modjump - n, n]
	xored = 0
	for i in range(xorrange[0], xorrange[1]):
		xored = xored ^ frow[i]
	jumprow = [xored]
	for i in range(1, n):
		xored = jumprow[i - 1]
		xored = xored ^ frow[(xorrange[0] + i - 1) % n]
		xored = xored ^ frow[(xorrange[1] + i - 1) % n]
		jumprow.append(xored)
	m = m - jump + 1
	frow = jumprow
print(' '.join(map(str, frow)))


(N, M) = map(int, input().split())
X = list(map(int, input().split()))
bit = 1
while bit < M:
	if M - 1 & bit:
		X = [X[i] ^ X[(i + bit) % N] for i in range(N)]
	bit <<= 1
print(' '.join(map(str, X)))


def row_shifts(m):
	(current_row, i) = (1, 0)
	while current_row < m:
		if current_row + 2 ** i <= m:
			yield i
			current_row += 2 ** i
			i += 1
		else:
			i -= 1

def get_matxor_m_row(row, n, m):
	for i in row_shifts(m):
		row = [row[ix] ^ row[(ix + 2 ** i) % n] for ix in range(n)]
	return row
(n, m) = map(int, input().split())
row = list(map(int, input().split()))
print(*get_matxor_m_row(row, n, m))


(n, m) = [int(x) for x in input().split()]
m -= 1
a = [int(x) for x in input().split()]
power = 1 << 63
while power > 0:
	if m & power:
		tmp = [a[i] ^ a[(i + power) % n] for i in range(n)]
		a = tmp
	power >>= 1
print(' '.join([str(x) for x in a]))


def bitize(x):
	L = []
	while x > 0:
		L.append(x % 2)
		x //= 2
	return L

def parity_of_nchoosek(n, k):
	t = n
	count = 0
	power = 2
	while power <= t:
		count += t // power
		power *= 2
	t = k
	power = 2
	while power <= t:
		count -= t // power
		power *= 2
	t = n - k
	power = 2
	while power <= t:
		count -= t // power
		power *= 2
	if count:
		return 0
	else:
		return 1

def compute_row(starting_row, r, n):
	new_row = [0 for i in range(0, n)]
	for i in range(0, n):
		current_choice = 1
		for j in range(0, r + 1):
			if current_choice % 2:
				new_row[i] ^= starting_row[(j + i) % n]
			current_choice *= r - j
			current_choice //= j + 1
	return new_row
(n, m) = [int(a) for a in input().split()]
first_row = [int(a) for a in input().split()]
s = ''

def compute_binary_row(n, starting_row, row_power_of_two):
	new_row = [0 for i in range(0, n)]
	for i in range(0, n):
		new_row[i] = starting_row[i] ^ starting_row[(i + pow(2, row_power_of_two)) % n]
	return new_row
bit_list = bitize(m - 1)
current_row = first_row
for b in range(0, len(bit_list)):
	if bit_list[b]:
		current_row = compute_binary_row(n, current_row, b)
for i in range(0, len(current_row)):
	s += str(current_row[i]) + ' '
print(s)


(n, m) = map(int, input().split())
ar = tuple(map(int, input().split()))
i = 1
m -= 1
while m:
	if m & 1:
		j = i % n
		ar = tuple((ar[pos] ^ ar[(pos + j) % n] for pos in range(n)))
	m >>= 1
	i <<= 1
print(*ar)


(l, t) = map(int, input().split())
c = list(map(int, input().split()))
t -= 1
s = 1
while t > 0:
	(t, b) = divmod(t, 2)
	if b:
		c = [c[i] ^ c[(i + s) % l] for i in range(l)]
	s *= 2
print(' '.join(map(str, c)))


import sys

def exp_matrix(n, m, arr):
	x = 0
	for cont in range(1, m):
		if pow(2, cont) > m - 1:
			break
		else:
			x = cont
	if x >= 1:
		proxlinha = []
		for pos in range(0, n):
			proxlinha.append(arr[pos] ^ arr[(pos + pow(2, x)) % n])
		proxlinha = exp_matrix(n, m - pow(2, x), proxlinha)
	elif m == 2:
		proxlinha = []
		for pos in range(0, n):
			proxlinha.append(arr[pos] ^ arr[(pos + 1) % n])
	else:
		proxlinha = arr.copy()
	return proxlinha
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
arr = list(map(int, input().strip().split(' ')))
result = exp_matrix(n, m, arr)
result = ' '.join(map(str, result))
print(result)


def shiftAndXor(arr, n):
	l = len(arr)
	return [arr[i] ^ arr[(i + n) % l] for i in range(l)]

def xorRing(arr, K):
	pow2 = 1
	while K > 0:
		if K % 2 == 1:
			arr = shiftAndXor(arr, pow2)
		K //= 2
		pow2 *= 2
	return arr
(n, m) = map(int, input().strip().split())
row = list(map(int, input().strip().split()))
print(' '.join([str(x) for x in xorRing(row, m - 1)]))


import os
import sys

def xorMatrix(m, first_row):
	n = len(first_row)
	row = first_row
	count = 0
	while m > 0:
		if m % 2 == 1:
			copy = [0] * n
			for i in range(n):
				copy[i] = row[i] ^ row[(i + 2 ** count) % n]
			row = copy
		count += 1
		m >>= 1
	return row
(n, m) = [int(s) for s in input().split()]
first_row = [int(s) for s in input().split()]
last_row = xorMatrix(m - 1, first_row)
print(' '.join([str(n) for n in last_row]))


(n, m) = map(int, input().split())
a = [int(x) for x in input().split()]
m -= 1
b = 1
while b < m:
	b <<= 1
while b:
	if b & m:
		a = [a[i] ^ a[(i + b) % n] for i in range(n)]
	b >>= 1
print(*a)


import math

def foo(a, n, m):
	if m == 1:
		return
	x = int(math.floor(math.log(m, 2)))
	if m == 2 ** x:
		x -= 1
	y = m - 2 ** x
	k = pow(2, x, n)
	b = [0] * n
	for i in range(n):
		b[i] = a[i] ^ a[(i + k) % n]
	for i in range(n):
		a[i] = b[i]
	foo(a, n, y)
(n, m) = list(map(int, input().split()))
a = list(map(int, input().split()))
foo(a, n, m)
print(' '.join([str(x) for x in a]))


(n, m) = map(int, input().split())
ar = tuple(map(int, input().split()))
i = 1
m -= 1
while m:
	if m & 1:
		j = i % n
		ar = tuple((ar[pos] ^ ar[(pos + j) % n] for pos in range(n)))
	m >>= 1
	i <<= 1
print(*ar)


(n, m) = map(int, input().split())
ar = tuple(map(int, input().split()))
i = 1
m -= 1
while m:
	if m & 1:
		j = i % n
		ar = tuple((ar[pos] ^ ar[(pos + j) % n] for pos in range(n)))
	m >>= 1
	i <<= 1
print(*ar)


(n, m) = map(int, input().split())
ar = tuple(map(int, input().split()))
i = 1
m -= 1
while m:
	if m & 1:
		j = i % n
		ar = tuple((ar[pos] ^ ar[(pos + j) % n] for pos in range(n)))
	m >>= 1
	i <<= 1
print(*ar)


(n, m) = map(int, input().split())
ar = tuple(map(int, input().split()))
i = 1
m -= 1
while m:
	if m & 1:
		j = i % n
		ar = tuple((ar[pos] ^ ar[(pos + j) % n] for pos in range(n)))
	m >>= 1
	i <<= 1
print(*ar)


(n, m) = map(int, input().split())
ar = tuple(map(int, input().split()))
i = 1
m -= 1
while m:
	if m & 1:
		j = i % n
		ar = tuple((ar[pos] ^ ar[(pos + j) % n] for pos in range(n)))
	m >>= 1
	i <<= 1
print(*ar)


(N, M) = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
S = f'{M - 1:064b}'
for i in range(len(S)):
	if S[i] == '1':
		delta = pow(2, 64 - i - 1, N)
		A = [A[j] ^ A[(j + delta) % N] for j in range(len(A))]
print(' '.join(map(str, A)))


(n, m) = map(int, input().split())
ar = tuple(map(int, input().split()))
i = 1
m -= 1
while m:
	if m & 1:
		j = i % n
		ar = tuple((ar[pos] ^ ar[(pos + j) % n] for pos in range(n)))
	m >>= 1
	i <<= 1
print(*ar)


(n, m) = map(int, input().split())
ar = tuple(map(int, input().split()))
i = 1
m -= 1
while m:
	if m & 1:
		j = i % n
		ar = tuple((ar[pos] ^ ar[(pos + j) % n] for pos in range(n)))
	m >>= 1
	i <<= 1
print(*ar)


(n, m) = map(int, input().split())
ar = tuple(map(int, input().split()))
i = 1
m -= 1
while m:
	if m & 1:
		j = i % n
		ar = tuple((ar[pos] ^ ar[(pos + j) % n] for pos in range(n)))
	m >>= 1
	i <<= 1
print(*ar)


(n, m) = map(int, input().split())
ar = tuple(map(int, input().split()))
i = 1
m -= 1
while m:
	if m & 1:
		j = i % n
		ar = tuple((ar[pos] ^ ar[(pos + j) % n] for pos in range(n)))
	m >>= 1
	i <<= 1
print(*ar)


import os
import sys
(n, m) = map(int, input().split())
ar = tuple(map(int, input().split()))
i = 1
m -= 1
while m:
	if m & 1:
		j = i % n
		ar = tuple((ar[pos] ^ ar[(pos + j) % n] for pos in range(n)))
	m >>= 1
	i <<= 1
print(*ar)


(n, m) = map(int, input().split())
ar = tuple(map(int, input().split()))
i = 1
m -= 1
while m:
	if m & 1:
		j = i % n
		ar = tuple((ar[pos] ^ ar[(pos + j) % n] for pos in range(n)))
	m >>= 1
	i <<= 1
print(*ar)


(n, m) = map(int, input().split())
ar = tuple(map(int, input().split()))
i = 1
m -= 1
while m:
	if m & 1:
		j = i % n
		ar = tuple((ar[pos] ^ ar[(pos + j) % n] for pos in range(n)))
	m >>= 1
	i <<= 1
print(*ar)