Jack and Daniel are friends.  They want to encrypt their conversations so that they can save themselves from interception by a detective agency so they invent a new cipher.  

Every message is encoded to its binary representation. Then it is written down $\boldsymbol{\mbox{k}}$ times, shifted by $0,1,\cdots,k-1$ bits. Each of the columns is XORed together to get the final encoded string.

If $b=1001011$ and $k=4$ it looks like so:  

1001011     shift 0 
01001011    shift 1
001001011   shift 2
0001001011  shift 3
----------
1110101001  <- XORed/encoded string s

Now we have to decode the message.  We know that $k=4$.  The first digit in $s=1$ so our output string is going to start with $1$.  The next two digits are also $1$, so they must have been XORed with $0$.  We know the first digit of our $4^{th}$ shifted string is a $\mbox{I}$ as well.  Since the $4^{th}$ digit of $\boldsymbol{\mathrm{~S~}}$ is $0$, we XOR that with our $1$ and now know there is a $1$ in the $4^{th}$ position of the original string.  Continue with that logic until the end.

Then the encoded message $\boldsymbol{\mathrm{~S~}}$ and the key $\boldsymbol{\mbox{k}}$ are sent to Daniel.   

Jack is using this encoding algorithm and asks Daniel to implement a decoding algorithm. 
Can you help Daniel implement this?  

Function Description  

Complete the cipher function in the editor below.  It should return the decoded string.  

cipher has the following parameter(s):  

k: an integer that represents the number of times the string is shifted 
s: an encoded string of binary digits

Input Format

The first line contains two integers $n$ and $\boldsymbol{\mbox{k}}$, the length of the original decoded string and the number of shifts. 

The second line contains the encoded string $\boldsymbol{\mathrm{~S~}}$ consisting of $n+k-1$ ones and zeros.  

Constraints

$1\leq n\leq10^{6}$ 

$1\leq k\leq10^6$ 

$|s|=n+k-1$ 

It is guaranteed that $\boldsymbol{\mathrm{~S~}}$ is valid.  

Output Format

Return the decoded message of length $n$, consisting of ones and zeros.  

Sample Input 0
7 4
1110100110

Sample Output 0
1001010

Explanation 0
1001010
 1001010
  1001010
   1001010
----------
1110100110

Sample Input 1
6 2
1110001

Sample Output 1
101111

Explanation 1
101111
 101111
-------
1110001

Sample Input 2
10 3
1110011011

Sample Output 2
10000101

Explanation 2

10000101
010000101

0010000101

1110011011

Difficulty: MEDIUM
Tags: Bit manipulation
Skill types: Bit manipulation

Starter code:

Solutions:
(n, k) = [int(i) for i in input().split()]
code = [int(i) for i in input()]
solution = [0] * n
xorSolution = 0
for i in range(n):
	if i >= k:
		xorSolution ^= solution[~(i - k)]
	i = ~i
	e = code[i]
	solution[i] ^= code[i] ^ xorSolution
	xorSolution ^= solution[i]
print(*solution, sep='')


(n, k) = [int(i) for i in input().split(' ')]
s = input()
curVal = 0
s = [ord(c) - 48 for c in s]
out = [s[0]]
curVal = s[0]
for i in range(1, len(s) - k + 1):
	if i >= k:
		curVal ^= out[i - k]
	newVal = curVal ^ s[i]
	out.append(newVal)
	curVal ^= newVal
print(''.join([str(i) for i in out]))


def xor(x, y):
	if x != y:
		return '1'
	return '0'
(n, k) = map(int, input().split())
s = input()[::-1]
x = '0'
res = ''
for i in range(n):
	if i - k >= 0:
		x = xor(x, res[i - k])
	if s[i] != x:
		res += '1'
	else:
		res += '0'
	x = s[i]
print(res[::-1])


import itertools, operator as op, sys
(N, K) = list(map(int, sys.stdin.readline().split()))
S = list(map(int, sys.stdin.readline().strip()))
(A, B) = ([S[0]], [S[0]])
for i in range(1, len(S) - K + 1):
	x = A[-1] ^ S[i]
	B.append(A[-K] ^ x if len(A) >= K else x)
	A.append(A[-1] ^ B[-1])
print(''.join(map(str, B)))


def decypher(encoded, K):
	size = len(encoded) - K + 1
	ans = encoded[0]
	tmp = int(encoded[0])
	for x in range(1, size):
		c = tmp ^ int(encoded[x])
		ans += str(c)
		tmp ^= c
		if x >= K - 1:
			tmp ^= int(ans[x - K + 1])
	print(ans)
(N, K) = map(int, input().split())
S = input()
decypher(S, K)


(n, k) = map(int, input().split())
s = int(input(), 2)
s ^= s << 1
while k < n:
	s ^= s << k
	k *= 2
s &= 2 ** n - 1
print(format(s, '0' + str(n) + 'b'))


(N, K) = map(int, input().split())
S = list(map(int, input()))
ans = [S[-1]]
for i in range(1, min(K, N)):
	temp = S[-i] ^ S[-i - 1]
	ans.append(temp)
for i in range(K, N):
	outbit = ans[i - K]
	temp = S[-i] ^ S[-i - 1] ^ outbit
	ans.append(temp)
while ans:
	print(ans.pop(), end='')


[n, k] = [int(x) for x in input().split()]
s = int(input(), 2)
m = s << 1 ^ s
x = m
count = k
while count < n:
	x = x << k ^ m
	count += k
print(bin(x)[-n:])


import itertools, operator as op, sys
(N, K) = list(map(int, sys.stdin.readline().split()))
S = list(map(int, sys.stdin.readline().strip()))
(A, B) = ([S[0]], [S[0]])
for i in range(1, len(S) - K + 1):
	x = A[-1] ^ S[i]
	B.append(A[-K] ^ x if len(A) >= K else x)
	A.append(A[-1] ^ B[-1])
print(''.join(map(str, B)))


import itertools, operator as op, sys
(N, K) = list(map(int, sys.stdin.readline().split()))
S = list(map(int, sys.stdin.readline().strip()))
(A, B) = ([S[0]], [S[0]])
for i in range(1, len(S) - K + 1):
	x = A[-1] ^ S[i]
	B.append(A[-K] ^ x if len(A) >= K else x)
	A.append(A[-1] ^ B[-1])
print(''.join(map(str, B)))


import itertools, operator as op, sys
(N, K) = list(map(int, sys.stdin.readline().split()))
S = list(map(int, sys.stdin.readline().strip()))
(A, B) = ([S[0]], [S[0]])
for i in range(1, len(S) - K + 1):
	x = A[-1] ^ S[i]
	B.append(A[-K] ^ x if len(A) >= K else x)
	A.append(A[-1] ^ B[-1])
print(''.join(map(str, B)))


(N, K) = list(map(int, input().split()))
v = list(map(int, list(input())))
v = v[::-1]
r = [v[0]]
a = 0
for i in range(1, N):
	a = a ^ r[-1]
	if i >= K:
		a = a ^ r[-K]
	r.append(a ^ v[i])
print(''.join(map(str, r[::-1])))


import itertools, operator as op, sys
(N, K) = list(map(int, sys.stdin.readline().split()))
S = list(map(int, sys.stdin.readline().strip()))
(A, B) = ([S[0]], [S[0]])
for i in range(1, len(S) - K + 1):
	x = A[-1] ^ S[i]
	B.append(A[-K] ^ x if len(A) >= K else x)
	A.append(A[-1] ^ B[-1])
print(''.join(map(str, B)))


import itertools, operator as op, sys
(N, K) = list(map(int, sys.stdin.readline().split()))
S = list(map(int, sys.stdin.readline().strip()))
(A, B) = ([S[0]], [S[0]])
for i in range(1, len(S) - K + 1):
	x = A[-1] ^ S[i]
	B.append(A[-K] ^ x if len(A) >= K else x)
	A.append(A[-1] ^ B[-1])
print(''.join(map(str, B)))


gxor = 0

def xor2(res, pos, k):
	global gxor
	if pos == 0:
		gxor = 0
		return 0
	if pos < k:
		ret = gxor ^ res[pos - 1]
		gxor = ret
	elif res[pos - 1] != res[pos - k]:
		gxor = int(gxor == 0)
		ret = gxor
	else:
		ret = gxor
	return ret

def xor1(res, pos, k):
	if pos == 0:
		return 0
	if pos < k:
		ret = 0
		for i in range(0, pos):
			ret ^= res[i]
	else:
		ret = res[pos - k]
		for i in range(pos - k, pos):
			ret ^= res[i]
	return ret
(n, k) = list(map(int, input().split()))
st = input()
st = st[::-1]
res = []
for i in range(n):
	v = xor2(res, i, k)
	if st[i] == '0' and v == 0:
		res.append(0)
	elif st[i] == '0' and v == 1:
		res.append(1)
	elif st[i] == '1' and v == 0:
		res.append(1)
	elif st[i] == '1' and v == 1:
		res.append(0)
for i in reversed(res):
	print('%d' % i, end='')


l = list(map(lambda s: int(s), input().split(' ')))
n = l[0]
k = l[1]
s = input()
res = s[0]
start = 0
end = 1
mask = int(res[0])
while end < len(s) - k + 1 and end - start < k:
	tmp = int(s[end]) ^ mask
	mask = mask ^ tmp
	end += 1
	res = res + str(tmp)
for pos in range(end, len(s) - k + 1):
	mask = mask ^ int(res[start])
	start += 1
	tmp = int(s[pos]) ^ mask
	mask = mask ^ tmp
	res = res + str(tmp)
print(res)


def xorN(x, n, k):
	if n <= k:
		return x
	return xorN((x ^ x << k) >> k, n, 2 * k)
(n, k) = [int(i) for i in input().strip().split()]
x = int(input(), 2)
x = (x ^ x << 1) >> k
res = format(xorN(x, n, k), 'b')
zero = '0' * (n - len(res))
print(zero + res)


(n, k) = [int(i) for i in input().split()]
s = input()
no1 = 0
ans = s[0]
if s[0] == '1':
	no1 = 1
j = 0
for i in range(1, len(s) - k + 1):
	if no1 % 2 == 0:
		if s[i] == '1':
			ans += '1'
			no1 += 1
		else:
			ans += '0'
	elif s[i] == '1':
		ans += '0'
	else:
		ans += '1'
		no1 += 1
	if i - j == k - 1:
		if ans[j] == '1':
			no1 -= 1
		j += 1
print(ans)


from collections import deque
(n, k) = (int(f) for f in input().split())
s = [int(f) for f in input()]
result = deque()
prev = deque((0 for _ in range(k - 1)))
acc = 0
for i in range(n):
	bit = s[-(i + 1)] % 2
	bit ^= acc
	result.appendleft(str(bit))
	acc ^= prev.popleft() ^ bit
	prev.append(bit)
print(''.join(result))


(N, K) = map(int, input().split())
ans = [0 for x in range(K - 1)]
S = list(map(int, input()))
S_count = K - 1
t = 0
for n in S:
	temp = n
	t = t ^ ans[S_count - K] ^ ans[S_count - 1]
	temp = temp ^ t
	ans.append(temp)
	S_count += 1
K = K - 1
ans = ans[K:0 - K]
for i in ans:
	print(i, end='')


import sys
(N, K) = tuple(map(int, input().split()))
iStr = tuple(map(int, tuple(input())))
rStr = [0] * N
if K == 1:
	print(''.join([str(x) for x in iStr]))
	sys.exit()
pSum = [0] * (N + 1)
for i in range(1, N + 1):
	pFrom = i - K if i >= K else 0
	pTo = i - 1
	prev = (pSum[pTo] - pSum[pFrom]) % 2
	curr = iStr[-i]
	if curr == 0:
		rStr[-i] = prev
	elif prev == 1:
		rStr[-i] = 0
	else:
		rStr[-i] = 1
	pSum[i] = pSum[i - 1] + rStr[-i]
print(''.join([str(x) for x in rStr]))