You are given a binary string S = S_{1S}_2 \ldots S_{N} of length N. You are also given an integer K. You can do the following operation at most N-K+1 times:
First, choose a substring S_{iS}_{i+1} \ldots S_{i+K-1} of S of length exactly K. This substring shouldn't have been chosen in any of the previous operations. That is, the same starting index of the substring can't be chosen twice.
Then, flip all the characters of the chosen substring (i.e. change every 0 to 1 and vice versa).

Find the lexicographically smallest string possible after the operations if you do them in an optimal way.

Note:
A substring is consecutive elements of a string. For eg. in the string "01011", "101" is a substring, but "111" is not a substring.
A string A is lexicographically smaller than string B, if A_{i} < B_{i}, where i is the first index where A and B differ.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- The first line of each test case contains two space-separated integers: N, K.
- The second line of each test case contains the string S.

------ Output Format ------ 

For each test case, output on a new line the lexicographically smallest string that you can achieve.

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

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 10^{5}$
$1 ≤ K ≤ N$
- Each element of $S$ is either $0$ or $1$
- The sum of $N$ over all test cases won't exceed $3 \times 10^{5}$.

------ subtasks ------ 

Subtask 1 (10 points): $1 ≤ M ≤ 10$
Subtask 2 (20 points): The sum of $N$ across all test cases won't exceed $20$.
Subtask 3 (70 points): No further constraints.

----- Sample Input 1 ------ 
4
3 2
101
4 2
1011
5 3
01010
5 2
01010

----- Sample Output 1 ------ 
000
0001
00011
00000

----- explanation 1 ------ 
Test case $1$: Choose the substring $1\textcolor{red}{01}$ and flip it. So now $S$ becomes $110$. Then choose the substring $\textcolor{red}{11}0$ and flip it. So now $S$ becomes $000$. This is the lexicographically smallest string that can be achieved, and hence this is the answer.

Test case $2$: Choose the substring $1\textcolor{red}{01}1$ and flip it. So now $S$ becomes $1101$. Then choose the substring $\textcolor{red}{11}01$ and flip it. So now $S$ becomes $0001$. This is the lexicographically smallest string that can be achieved, and hence this is the answer.

Test case $3$: Choose the substring $0\textcolor{red}{101}0$ and flip it. So now $S$ becomes $00100$. Then choose the substring $00\textcolor{red}{100}$ and flip it. So now $S$ becomes $00011$. This is the lexicographically smallest string that can be achieved, and hence this is the answer.

Test case $4$: Choose the substring $01\textcolor{red}{01}0$ and flip it. So now $S$ becomes $01100$. Then choose the substring $0\textcolor{red}{11}00$ and flip it. So now $S$ becomes $00000$. This is the lexicographically smallest string that can be achieved, and hence this is the answer.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Data structures

Amortized analysis

Range queries

Greedy algorithms


Solutions:
T = int(input())
for t in range(T):
	(n, k) = input().split(' ')
	n = int(n)
	k = int(k)
	s = input()
	arr = []
	for i in range(n):
		arr.append(s[i])
	prefarr = [0 for i in range(n)]
	c = 0
	a = n - k + 1
	for i in range(n - k + 1):
		if arr[i] == '0' and (c + prefarr[i]) % 2 == 0:
			c += prefarr[i]
			continue
		elif arr[i] == '1' and (c + prefarr[i]) % 2 != 0:
			c += prefarr[i]
			continue
		else:
			prefarr[i] += 1
			if i + k < n:
				prefarr[i + k] -= 1
			c += prefarr[i]
			a -= 1
		if a == 0:
			break
	for i in range(1, len(prefarr)):
		prefarr[i] += prefarr[i - 1]
	ans = ''
	for i in range(len(prefarr)):
		if arr[i] == '0' and prefarr[i] % 2 == 0 or (arr[i] == '1' and prefarr[i] % 2 != 0):
			ans += '0'
		else:
			ans += '1'
	print(ans)
	print('')


def solve(n, k, s):
	arr = [i for i in s]
	pre = [0 for i in range(n + 1)]
	if arr[0] == '1':
		arr[0] = '0'
		pre[0] += 1
		pre[0 + k] -= 1
	for i in range(1, n):
		pre[i] += pre[i - 1]
		if pre[i] % 2 == 1:
			if arr[i] == '0':
				arr[i] = '1'
			else:
				arr[i] = '0'
		if i + k <= n:
			if arr[i] == '1':
				arr[i] = '0'
				pre[i] += 1
				pre[i + k] -= 1
	p = ''
	for i in arr:
		p += i
	return p
t = int(input())
while t > 0:
	t -= 1
	(n, k) = map(int, input().split())
	s = str(input())
	print(solve(n, k, s))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	inds = [0] * (n + 1)
	if s[0] == '1':
		inds[0] = 1
		inds[k] = -1
	for i in range(1, n):
		inds[i] += inds[i - 1]
		if i <= n - k and int(s[i]) ^ inds[i] % 2:
			inds[i] += 1
			inds[i + k] -= 1
	res = ''
	for i in range(n):
		res += str(int(s[i]) ^ inds[i] % 2)
	print(res)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = [int(x) for x in input()]
	s = 0
	pre = [0] * n
	for i in range(n):
		if i - k >= 0:
			s -= pre[i - k]
		if i < n - k + 1:
			if s % 2 == 0 and arr[i] == 1:
				s += 1
				pre[i] = 1
			elif s % 2 != 0 and arr[i] == 0:
				s += 1
				pre[i] = 1
			print(0, end='')
		elif s % 2 == 0:
			print(arr[i], end='')
		else:
			print(arr[i] ^ 1, end='')
	print()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	ans = []
	moves = []
	ptr = 0
	for i in range(n):
		while ptr < len(moves):
			if moves[ptr] + k <= i:
				ptr += 1
			else:
				break
		cur = 0 if s[i] == '0' else 1
		changes = len(moves) - ptr
		cur ^= changes % 2
		if i + k > n:
			ans.append(cur)
		else:
			ans.append(0)
			if cur == 1:
				moves.append(i)
	print(''.join((str(x) for x in ans)))


T = int(input())
for i in range(T):
	(N, K) = input().split()
	(N, K) = (int(N), int(K))
	string = input()
	arr = [0 for i in range(len(string))]
	j = 0
	new_string = ''
	sum = 0
	while j < len(string) - K + 1:
		if j >= K:
			sum -= arr[j - K]
		if sum % 2 == 0 and string[j] == '1':
			arr[j] = 1
			sum += 1
		elif sum % 2 == 1 and string[j] == '0':
			arr[j] = 1
			sum += 1
		new_string += '0'
		j += 1
	while j < len(string):
		if j >= K:
			sum -= arr[j - K]
		if sum % 2 == 0 and string[j] == '1':
			arr[j] = 1
			new_string += '1'
		elif sum % 2 == 1 and string[j] == '0':
			arr[j] = 1
			new_string += '1'
		else:
			new_string += '0'
		j += 1
	print(new_string)


def f(s, k):
	n = len(s)
	arr = list(s)
	negatives = set()
	m = 0
	for i in range(n):
		if i in negatives:
			m -= 1
		if (int(arr[i]) + m) % 2 == 0:
			arr[i] = '0'
			continue
		if i >= n - k + 1:
			arr[i] = '1'
			continue
		m += 1
		negatives.add(i + k)
		arr[i] = '0'
	return ''.join(arr)
t = int(input())
for i in range(t):
	(n, k) = [int(el) for el in input().split(' ')]
	s = input()
	print(f(s, k))


from collections import deque
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	i = 0
	queue = deque()
	ans = ''
	while i < n:
		while queue and queue[0] < i - k + 1:
			queue.popleft()
		if i + k <= n:
			if len(queue) % 2 == 0 and s[i] == '1' or (len(queue) % 2 and s[i] == '0'):
				queue.append(i)
			ans += '0'
		elif len(queue) % 2 == 0 and s[i] == '1' or (len(queue) % 2 and s[i] == '0'):
			ans += '1'
		else:
			ans += '0'
		i += 1
	print(ans)


q = int(input())
for _ in range(q):
	(n, k) = map(int, input().split())
	s = input().strip()
	s = list(s)
	count = 0
	flips = {}
	for i in range(n - k + 1):
		if (int(s[i]) + count) % 2 == 0:
			s[i] = '0'
		else:
			s[i] = '0'
			count += 1
			flips[i + k - 1] = 1
		if flips.get(i):
			count -= 1
	for i in range(n - k + 1, n):
		if (int(s[i]) + count) % 2 == 0:
			s[i] = '0'
		else:
			s[i] = '1'
		if flips.get(i):
			count -= 1
	print(''.join(s))


from sys import stdin
input = stdin.readline
test = int(input())
for _ in range(test):
	(n, k) = map(int, input().split())
	s = input().strip()
	a = list(s)
	c = 0
	d = {}
	for i in range(n - k + 1):
		if (int(a[i]) + c) % 2 == 0:
			a[i] = '0'
		else:
			a[i] = '0'
			c += 1
			d[i + k - 1] = 1
		if d.get(i):
			c -= 1
	for i in range(n - k + 1, n):
		if (int(a[i]) + c) % 2 == 0:
			a[i] = '0'
		else:
			a[i] = '1'
		if d.get(i):
			c -= 1
	ans = ''.join(a)
	print(ans)


for testcase in range(int(input())):
	(n, k) = map(int, input().split())
	string = input()
	arr = [0] * n
	rstring = ''
	for (idx, i) in enumerate(string):
		if idx == 0:
			if i == '1':
				arr[idx] = 1
				if idx + k <= n - 1:
					arr[idx + k] = -1
			rstring += '0'
			continue
		el = ((arr[idx - 1] + arr[idx]) % 2 + int(i)) % 2
		arr[idx] = arr[idx - 1] + arr[idx]
		if el == 1:
			if idx + k <= n:
				arr[idx] += 1
			if idx + k < n:
				arr[idx + k] = -1
		if arr[idx] % 2:
			rstring += '1' if i == '0' else '0'
		else:
			rstring += i
	print(rstring)


T = int(input())
for _ in range(T):
	(n, k) = list(map(int, input().split()))
	s = input()
	s = list(s)
	i = 1
	pref = [0 for j in range(n + 1)]
	if s[0] == '1':
		pref[0] = 1
		pref[k] = -1
		s[0] = '0'
	while i < len(s):
		pref[i] += pref[i - 1]
		if pref[i] % 2 == 1:
			s[i] = str(int(s[i]) ^ 1)
		if i + k - 1 < len(s):
			if s[i] == '1':
				pref[i] += 1
				s[i] = '0'
				pref[i + k] -= 1
		i += 1
	print(''.join(s))


t = int(input())
for i in range(t):
	[N, K] = [int(i) for i in input().split()]
	s = input()
	fliparr = [-1] * N
	length = 0
	flip = 0
	for i in range(N - K + 1):
		if i == 0:
			if s[i] == '1':
				flip += 1
				fliparr[i] = flip
			else:
				fliparr[i] = flip
		else:
			if max(0, i - K + 1) == 0:
				if fliparr[0] == 1:
					val = fliparr[i - 1] - fliparr[0] + 1
				else:
					val = fliparr[i - 1] - fliparr[0]
			elif fliparr[i - K + 1] == fliparr[i - K]:
				val = fliparr[i - 1] - fliparr[i - K + 1]
			else:
				val = fliparr[i - 1] - fliparr[i - K + 1] + 1
			if s[i] == '1' and val % 2 == 0:
				flip += 1
				fliparr[i] = flip
			if s[i] == '0' and val % 2 == 1:
				flip += 1
				fliparr[i] = flip
			if s[i] == '1' and val % 2 == 1:
				fliparr[i] = flip
			if s[i] == '0' and val % 2 == 0:
				fliparr[i] = flip
	if N == 1:
		print(0)
	elif N > K:
		for i in range(N - K + 1, N):
			if max(0, i - K + 1) == 0:
				if fliparr[0] == 1:
					val = fliparr[N - K]
				else:
					val = fliparr[N - K]
			elif max(0, i - K + 1) == i - K + 1:
				if fliparr[i - K] == fliparr[i - K + 1]:
					val = fliparr[N - K] - fliparr[i - K + 1]
				else:
					val = fliparr[N - K] - fliparr[i - K + 1] + 1
			if val % 2 == 0:
				if s[i] == '0':
					fliparr[i] = 0
				else:
					fliparr[i] = 1
			elif s[i] == '0':
				fliparr[i] = 1
			else:
				fliparr[i] = 0
		ans = [0] * (N - K + 1)
		for i in range(N - K + 1, N):
			ans.append(fliparr[i])
		for i in ans:
			print(i, end='')
		print()
	elif N == K:
		ans = [0]
		if s[0] == '0':
			for i in range(1, N):
				ans.append(int(s[i]))
		else:
			for i in range(1, N):
				if int(s[i]) == 0:
					ans.append(1)
				else:
					ans.append(0)
		for i in ans:
			print(i, end='')
		print()


def func1():
	(N, K) = map(int, input().split())
	s = list(input())
	flipped = [0 for i in range(N)]
	limit = N + K - 1
	flipct = 0
	ct = 0
	for i in range(N):
		if i >= K and flipped[i - K]:
			flipct -= 1
		if flipct & 1:
			if s[i] == '0':
				s[i] = '1'
			else:
				s[i] = '0'
		if s[i] == '1' and ct < limit and (i <= N - K):
			flipped[i] = '1'
			flipct += 1
			s[i] = '0'
			ct += 1
	print(''.join(s))
for _ in range(int(input())):
	func1()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(input())
	flip = [0] * (n + 1)
	if s[0] == '1':
		flip[0] = 1
		flip[k - 1] = -1
		s[0] = '0'
	sm = flip[0]
	for i in range(1, n - k + 1):
		if sm % 2:
			if s[i] == '0':
				flip[i] += 1
				flip[i + k - 1] -= 1
			else:
				s[i] = '0'
		elif s[i] == '1':
			s[i] = '0'
			flip[i] += 1
			flip[i + k - 1] -= 1
		sm += flip[i]
	for i in range(n - k + 1, n):
		if sm % 2:
			if s[i] == '1':
				s[i] = '0'
			else:
				s[i] = '1'
		sm += flip[i]
	print(''.join(s))


import collections as clts
import math
import heapq

def gcd(x, y):
	if y == 0:
		return x
	else:
		return gcd(y, x % y)

def lcm(x, y):
	return int(x / gcd(x, y) * y)
for _ in range(int(input())):
	(N, K) = list(map(int, input().split()))
	S = input()
	opQ = clts.deque()
	opt = []
	i = 0
	j = 0
	while i <= N - K + 1 and j <= N - 1:
		bit = S[j]
		while len(opQ) != 0:
			e = opQ.popleft()
			if e >= j - K + 1:
				opQ.appendleft(e)
				break
		if len(opQ) % 2 == 1 and bit == '1':
			bit = '0'
		elif len(opQ) % 2 == 0 and bit == '1':
			if j + K <= N:
				bit = '0'
				opQ.append(j)
				i += 1
		elif len(opQ) % 2 == 1 and bit == '0':
			bit = '1'
			if j + K <= N:
				bit = '0'
				opQ.append(j)
				i += 1
		else:
			bit = bit
		opt.append(bit)
		j += 1
	if j < N - 1:
		for i in range(j, N):
			opt.append(S[i])
	print(''.join(opt))


from collections import deque

def solve(word, n, k):
	ans = ''
	dq = deque()
	for i in range(n - k + 1):
		while len(dq) > 0 and dq[0] < i - k + 1:
			_ = dq.popleft()
		cnt = len(dq)
		if cnt % 2 == 0:
			if word[i] == '1':
				dq.append(i)
		elif word[i] == '0':
			dq.append(i)
		ans += '0'
	for i in range(n - k + 1, n):
		while len(dq) > 0 and dq[0] < i - k + 1:
			_ = dq.popleft()
		cnt = len(dq)
		if cnt % 2 == 0:
			ans += word[i]
		elif word[i] == '1':
			ans += '0'
		else:
			ans += '1'
	return ans
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	word = list(input())
	print(solve(word, n, k))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	ans = '0' * (n - k + 1)
	lc = []
	count = 0
	for i in range(n - k + 1):
		if i >= k:
			count -= lc[i - k]
		if s[i] == '1' and count % 2 == 0:
			lc.append(1)
			count += 1
		elif s[i] == '0' and count % 2 == 1:
			lc.append(1)
			count += 1
		else:
			lc.append(0)
	for i in range(n - k + 1, n):
		if i >= k:
			count -= lc[i - k]
		if count % 2 == 0:
			ans += s[i]
		elif s[i] == '1':
			ans += '0'
		else:
			ans += '1'
	print(ans)


from collections import deque
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	q = deque()
	i = 0
	j = k - 1
	count = 0
	res = 0
	ans = []
	while j < n and count < n - k + 1:
		if i > k - 1:
			res -= q.popleft()
		if s[i] == '0':
			if res % 2:
				ans.append('0')
				res += 1
				q.append(1)
			else:
				ans.append('0')
				q.append(0)
		elif res % 2:
			ans.append('0')
			q.append(0)
		else:
			ans.append('0')
			q.append(1)
			res += 1
		i += 1
		j += 1
		count += 1
	while i < j:
		if i > k - 1:
			res -= q.popleft()
		if s[i] == '0':
			if res % 2:
				ans.append('1')
			else:
				ans.append('0')
		elif res % 2:
			ans.append('0')
		else:
			ans.append('1')
		i += 1
	for i in range(len(ans), n):
		ans.append(s[i])
	print(''.join(ans))


for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	s = list(input())
	flipped = [0 for i in range(n)]
	flipcount = 0
	count = 0
	limit = n - k + 1
	for i in range(n):
		if i >= k and flipped[i - k]:
			flipcount -= 1
		if flipcount % 2 != 0:
			if s[i] == '1':
				s[i] = '0'
			else:
				s[i] = '1'
		if s[i] == '1' and count <= limit and (i <= n - k):
			flipped[i] = 1
			flipcount += 1
			count += 1
			s[i] = '0'
	print(''.join(s))


from collections import defaultdict
import math as m
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	fliped = [0] * n
	s = list(input())
	cnt = 0
	flipcnt = 0
	limit = n - k + 1
	for i in range(n):
		if i >= k and fliped[i - k]:
			flipcnt -= 1
		if flipcnt & 1:
			if s[i] == '1':
				s[i] = '0'
			else:
				s[i] = '1'
		if s[i] == '1' and cnt < limit and (i <= n - k):
			fliped[i] = 1
			flipcnt += 1
			s[i] = '0'
			cnt += 1
	print(''.join(s))


for j in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	s = list(s)
	fliped = [0] * n
	flipcount = 0
	count = 0
	limit = n - k + 1
	for i in range(n):
		if i >= k and fliped[i - k]:
			flipcount -= 1
		if flipcount & 1:
			if s[i] == '0':
				s[i] = '1'
			else:
				s[i] = '0'
		if s[i] == '1' and count < limit and (i <= n - k):
			fliped[i] = 1
			flipcount += 1
			s[i] = '0'
			count += 1
	print(''.join(s))


t = int(input())
for _ in range(0, t):
	temp = input().split()
	(n, k) = (int(temp[0]), int(temp[1]))
	s = list(input())
	queue = []
	for i in range(n):
		s[i] = int(s[i])
		while len(queue) > 0:
			if queue[0] < i:
				queue.pop(0)
			else:
				break
		s[i] = (s[i] + len(queue)) % 2
		if s[i] == 0:
			continue
		if i < n - k + 1:
			s[i] = 1 - s[i]
			queue.append(i + k - 1)
	print(''.join(map(str, s)))


from operator import xor
import random
import math
from collections import defaultdict, Counter
from functools import lru_cache
import bisect
import heapq

class SegmentTree:

	def __init__(self, nums):
		self._size = len(nums)
		self._tree = [0] * (4 * self._size)
		self.build(nums)

	def build(self, a, v=1, lo=0, hi=None):
		if hi is None:
			hi = self._size - 1
		if lo == hi:
			self._tree[v] = a[lo]
		else:
			mi = (lo + hi) // 2
			self.build(a, 2 * v, lo, mi)
			self.build(a, 2 * v + 1, mi + 1, hi)
			self._tree[v] = self._tree[2 * v] + self._tree[2 * v + 1]

	def update(self, pos, val, v=1, lo=0, hi=None):
		if hi is None:
			hi = self._size - 1
		if lo == hi:
			self._tree[v] = val
		else:
			mi = (lo + hi) // 2
			if pos <= mi:
				self.update(pos, val, 2 * v, lo, mi)
			else:
				self.update(pos, val, 2 * v + 1, mi + 1, hi)
			self._tree[v] = self._tree[2 * v] + self._tree[2 * v + 1]

	def query(self, l, h, v=1, lo=0, hi=None):
		if hi is None:
			hi = self._size - 1
		if l > h:
			return 0
		elif l == lo and h == hi:
			return self._tree[v]
		else:
			mi = (lo + hi) // 2
			return self.query(l, min(mi, h), 2 * v, lo, mi) + self.query(max(mi + 1, l), h, 2 * v + 1, mi + 1, hi)

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = list(range(n))

	def find(self, x):
		if self.parents[x] == x:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x != y:
			self.parents[x] = y
dire = [0, 1, 0, -1, 0]

def is_prime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def google(t):
	print('Case #{}:'.format(t), end=' ')
RANDOM = random.randrange(2 ** 62)

def Wrapper(x):
	return x ^ RANDOM

def solve():
	(n, k) = map(int, input().split())
	b = input()
	dp = [0] * (n + 1)
	for i in range(n + 1):
		dp[i] += dp[i - 1]
		if i <= n - k and (b[i] == '1') ^ dp[i] % 2:
			dp[i] += 1
			dp[i + k] -= 1
		dp[i] = dp[i] % 2
	ans = ''
	for i in range(n):
		if dp[i] == 1:
			ans += '1' if b[i] == '0' else '0'
		else:
			ans += b[i]
	print(ans)
for t in range(int(input())):
	solve()


import numpy as np
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, list(input())))
	b = np.array(a)
	for i in range(n - k + 1):
		if b[i] == 1:
			b[i:i + k] = 1 - b[i:i + k]
	q = list(map(str, b))
	print(*q, sep='')


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	B = list(input())
	flipCount = 0
	fliped = [0] * N
	for i in range(N):
		if i - K >= 0 and fliped[i - K]:
			flipCount -= 1
		if flipCount % 2:
			if B[i] == '0':
				B[i] = '1'
			else:
				B[i] = '0'
		if B[i] == '1' and i < N - K + 1:
			fliped[i] = 1
			flipCount += 1
			B[i] = '0'
	print(''.join(B))


def sol():
	[n, k] = map(int, input().split(' '))
	sk = input()
	s = int(sk, 2)
	kn = '1' * k
	kn = int(kn, 2)
	tkn = kn
	kn = kn << n - k
	while tkn != kn:
		if s ^ kn < s:
			s = s ^ kn
		kn = kn >> 1
	if s ^ kn < s:
		s = s ^ kn
	ans = ''
	for i in range(n):
		if s & 1 == 1:
			ans = ans + '1'
		else:
			ans = ans + '0'
		s = s >> 1
	print(ans[::-1])
t = int(input())
while t:
	sol()
	t = t - 1


import numpy as np

def func(string, N, K):
	for i in range(N - K + 1):
		if string[i] == 1:
			string[i:i + K] = 1 - string[i:i + K]
	string = list(map(str, string))
	return ''.join(string)
t = int(input())
for _ in range(t):
	(N, K) = list(map(int, input().split()))
	string = list(map(int, list(input())))
	string = np.array(string)
	print(func(string, N, K))


import heapq
t = int(input())
while t:
	s = input().split()
	(n, k) = map(int, s)
	s = input()
	dp = [0 for i in range(n)]
	ans = ''
	flipCount = 0
	for i in range(n - k + 1):
		see = s[i]
		if flipCount % 2 == 0:
			act = see
		else:
			act = '1' if see == '0' else '0'
		if act == '1':
			dp[i] = 1
			flipCount += 1
		ans += '0'
		if i - k + 1 >= 0:
			flipCount -= dp[i - k + 1]
	for i in range(n - k + 1, n):
		see = s[i]
		if flipCount % 2 == 0:
			act = see
		else:
			act = '1' if see == '0' else '0'
		ans += act
		if i - k + 1 >= 0:
			flipCount -= dp[i - k + 1]
	print(ans)
	t -= 1


from sys import stdin, stdout
t = stdin.readline()
for _ in range(int(t)):
	(n, k) = [int(x) for x in stdin.readline().split()]
	b = list(map(int, *stdin.readline().split()))
	d = 0
	q = []
	while d <= n - k + 1:
		for i in range(n):
			for a in q:
				if a < i - k + 1:
					q.remove(a)
				else:
					break
			if len(q) % 2 == 0:
				if b[i] == 1:
					if i <= n - k:
						b[i] = 0
						q.append(i)
						d += 1
			elif b[i] == 0:
				if i <= n - k:
					q.append(i)
					d += 1
				else:
					b[i] = 1
			else:
				b[i] = 0
		break
	print(''.join(map(str, b)))


t = int(input())
for k in range(t):
	(n, k) = map(int, input().split())
	s = list(input())
	s.insert(0, 0)
	a = [0] * (2 * n + 1)
	t = 0
	for i in range(1, n - k + 2):
		if (int(s[i]) + t) % 2 == 1:
			t += 1
			a[i + k - 1] = 1
		t -= a[i]
		s[i] = 0
	for i in range(n - k + 2, n + 1):
		s[i] = (int(s[i]) + t) % 2
		t -= a[i]
	for i in range(1, n + 1):
		print(s[i], end='')
	print()


import math, sys
from collections import Counter, defaultdict, deque
from heapq import heapify, heappush, heappop
from bisect import bisect_left
INF = float('inf')

def solve():
	(n, k) = map(int, input().split())
	arr = list(map(int, input()))
	s = []
	for i in range(n - k + 1):
		j = len(s) - bisect_left(s, i - k + 1)
		if j % 2 == 1:
			arr[i] ^= 1
		if arr[i]:
			arr[i] = 0
			s.append(i)
	for i in range(n - k + 1, n):
		j = len(s) - bisect_left(s, i - k + 1)
		if j % 2 == 1:
			arr[i] ^= 1
	print(*arr, sep='')

def input():
	return sys.stdin.readline().rstrip('\n').strip()

def print(*args, sep=' ', end='\n'):
	first = True
	for arg in args:
		if not first:
			sys.stdout.write(sep)
		sys.stdout.write(str(arg))
		first = False
	sys.stdout.write(end)
ts = 1
ts = int(input())
for t in range(1, ts + 1):
	solve()


import math
t = int(input())
while t:
	(n, k) = map(int, input().split())
	l = list(input())
	ans = []
	flips = 0
	for i in range(n):
		if i >= k - 1 and i < n - k + 1:
			ans.append(flips)
			if l[i] == '1' and (flips - ans[i - k + 1]) % 2 == 0 or (l[i] == '0' and (flips - ans[i - k + 1]) % 2 != 0):
				l[i] = '0'
				flips += 1
			else:
				l[i] = '0'
		elif i < min(k - 1, n - k + 1):
			ans.append(flips)
			if l[i] == '1' and flips % 2 == 0 or (l[i] == '0' and flips % 2 != 0):
				l[i] = '0'
				flips += 1
			else:
				l[i] = '0'
		elif i - k + 1 >= 0:
			if (flips - ans[i - k + 1]) % 2 != 0:
				if l[i] == '1':
					l[i] = '0'
				else:
					l[i] = '1'
		elif flips % 2 != 0:
			if l[i] == '1':
				l[i] = '0'
			else:
				l[i] = '1'
	print(''.join(l))
	t -= 1


import bisect
for _ in range(int(input())):
	(str_len, flip_len) = [int(num) for num in input().split()]
	binary_str = input()
	flips = []
	result = []
	for i in range(str_len):
		first_flip_idx = bisect.bisect_right(flips, i - flip_len)
		last_flip_idx = bisect.bisect_left(flips, i)
		flips_num = last_flip_idx - first_flip_idx
		flip_possible = i <= str_len - flip_len
		flip_required = int(binary_str[i]) and flips_num % 2 == 0 or (not int(binary_str[i]) and flips_num % 2 != 0)
		if flip_possible and flip_required:
			flips.append(i)
			flips_num += 1
		if int(binary_str[i]) and flips_num % 2 != 0 or (not int(binary_str[i]) and flips_num % 2 == 0):
			result.append('0')
		else:
			result.append('1')
	print(''.join(result))


from sys import stdin
input = stdin.readline
l = int(input())
for _ in range(l):
	(o, k) = map(int, input().split())
	s = input().strip()
	q = list(s)
	count = 0
	t = {}
	for i in range(o - k + 1):
		if (int(q[i]) + count) % 2 == 0:
			q[i] = '0'
		else:
			q[i] = '0'
			count += 1
			t[i + k - 1] = 1
		if t.get(i):
			count -= 1
	for i in range(o - k + 1, o):
		if (int(q[i]) + count) % 2 == 0:
			q[i] = '0'
		else:
			q[i] = '1'
		if t.get(i):
			count -= 1
	answer = ''.join(q)
	print(answer)


from sys import stdin
input = stdin.readline
test = int(input())
for _ in range(test):
	(n, k) = map(int, input().split())
	s = input().strip()
	a = list(s)
	c = 0
	d = {}
	for i in range(n - k + 1):
		if (int(a[i]) + c) % 2 == 0:
			a[i] = '0'
		else:
			a[i] = '0'
			c += 1
			d[i + k - 1] = 1
		if d.get(i):
			c -= 1
	for i in range(n - k + 1, n):
		if (int(a[i]) + c) % 2 == 0:
			a[i] = '0'
		else:
			a[i] = '1'
		if d.get(i):
			c -= 1
	ans = ''.join(a)
	print(ans)

class Graph:

	def __init__(self):
		self.graph = defaultdict(list)

	def addEdge(self, u, v):
		self.graph[u].append(v)

	def DFSUtil(self, v, visited):
		visited.add(v)
		print(v, end=' ')
		for neighbour in self.graph[v]:
			if neighbour not in visited:
				self.DFSUtil(neighbour, visited)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	A = list(map(int, input()))
	t = 0
	a = [0] * 2 * N
	for i in range(0, N - K + 1):
		if (A[i] + t) % 2 == 1:
			t += 1
			a[i + K - 1] = 1
		t -= a[i]
		A[i] = 0
	for j in range(N - K + 1, N):
		A[j] = (A[j] + t) % 2
		t -= a[j]
	for i in range(0, N):
		print(A[i], end='')
	print()


T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	S = list(input())
	A = [0] * (2 * N + 1)
	X = 0
	for i in range(N - K + 1):
		if (int(S[i]) + X) % 2 == 1:
			X += 1
			A[i + K - 1] = 1
		X -= A[i]
		S[i] = 0
	i = N - K + 2
	res = []
	for i in range(N - K + 1, N):
		S[i] = (int(S[i]) + X) % 2
		X -= A[i]
	for i in range(N):
		res.append(str(S[i]))
	print(''.join(res))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	q = input()
	s = list(q)
	for i in range(len(q)):
		s[i] = int(s[i])
	a = [0] * (2 * n)
	t = 0
	for i in range(n - k + 1):
		if (s[i] + t) % 2 == 1:
			t += 1
			a[i + k - 1] = 1
		t -= a[i]
		s[i] = 0
	for i in range(n - k + 1, n):
		s[i] = 0 + (s[i] + t) % 2
		t -= a[i]
	for i in range(len(s)):
		s[i] = str(s[i])
	print(''.join(s))


import numpy as np
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	a = np.zeros((n,), dtype=int)
	one = np.ones((n,), dtype=int)
	for (i, v) in enumerate(s):
		a[i] = int(v)
	for i in np.arange(n - k + 1):
		if a[i] == 1:
			a[i:i + k] = a[i:i + k] ^ one[i:i + k]
	for i in a:
		print(i, end='')
	print()


for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	s = input()
	pre = 0
	ans = ''
	a = [0] * (n + 1)
	for i in range(n):
		pre += a[i]
		pre %= 2
		cur = ord(s[i]) - ord('0')
		if i < n - k + 1:
			ans += '0'
			a[i + k] -= pre ^ cur
			pre += pre ^ cur
			pre %= 2
		else:
			ans += str(pre ^ cur)
	print(ans)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	sr = input()
	s = []
	for i in sr:
		s.append(int(i))
	A = [0] * (2 * n)
	a = 0
	for i in range(1, n - k + 2):
		if (int(s[i - 1]) + a) % 2 == 1:
			a += 1
			A[i + k - 1] = 1
		a -= A[i]
		s[i - 1] = 48
	for i in range(n - k + 2, n + 1):
		s[i - 1] = 48 + (s[i - 1] + a) % 2
		a -= A[i]
	l = ''
	for i in s:
		l += str(i - 48)
	print(l)


T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	S = input()
	s = []
	flag = 0
	marker = 0
	maxi = 9999
	mini = -9999
	bool = True
	for i in S:
		flag += 1
		s.append(int(i))
		maxi -= flag
		mini += flag
	t = 0
	Bool = False
	check = 1
	a = []
	for i in range(0, 2 * N):
		check += maxi
		bool = True
		a.append(0)
	checker = -1
	marker -= check
	for i in range(0, N - K + 1):
		Bool = True
		if (int(s[i]) + t) % 2 == 1:
			marker -= 1
			t += 1
			flag += mini
			maxi -= marker
			a[i + K - 1] = 1
			marker += check
		t -= a[i]
		check += 1
		s[i] = 0
		marker += check
	for i in range(N - K + 1, N):
		check -= 1
		marker += maxi
		mini += maxi
		s[i] = (int(s[i]) + t) % 2
		t -= a[i]
		marker -= 99
	ans = ''
	rest = 'api'
	for i in range(N):
		check += 1
		Bool = False
		bool = True
		ans += str(s[i])
		marker -= flag
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s1 = list(map(int, input()))
	s = [None] + s1
	x = 0
	a = [0] * (2 * n + 1)
	for i in range(1, n - k + 2):
		if (s[i] + x) % 2 == 1:
			x += 1
			a[i + k - 1] = 1
		x -= a[i]
		s[i] = 48
	for i in range(n - k + 2, n + 1):
		s[i] = (48 + s[i] + x) % 2
		x -= a[i]
	for i in range(1, n + 1):
		print(s[i] % 2, end='')
	print()


from collections import Counter
import math

def solve():
	(n, k) = map(int, input().split(' '))
	lst = list(map(int, list(input())))
	smLst = []
	for i in range(n):
		smLst.append(0)
	temp = 0
	for i in range(n - k + 1):
		if (lst[i] + temp) % 2 == 1:
			smLst[i + k - 1] = 1
			temp += 1
		temp -= smLst[i]
		lst[i] = 12
	for i in range(n - k + 1, n):
		lst[i] = 12 + (lst[i] + temp) % 2
		temp -= smLst[i]
	for i in range(n):
		lst[i] -= 12
	lst = list(map(str, lst))
	s = ''.join(lst)
	print(s)
t = int(input())
for _ in range(t):
	solve()


import os.path
from math import gcd, floor, ceil, log2
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

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

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

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
for _ in range(int(input())):
	(n, k) = mp()
	s = list(input())
	t = 0
	a = [0] * (2 * n + 1)
	for i in range(n - k + 1):
		if (int(s[i]) + t) % 2 == 1:
			t += 1
			a[i + k - 1] = 1
		t -= a[i]
		s[i] = chr(48)
	for i in range(n - k + 1, n):
		s[i] = chr(48 + (int(s[i]) + t) % 2)
		t -= a[i]
	p = ''
	for i in s:
		p += i
	print(p)


t = int(input())
for _ in range(t):
	(a, b) = map(int, input().strip().split(' '))
	s = input()
	ans = ''
	c = 0
	li = [0 for i in range(a + 1)]
	for i in range(a):
		c = c + li[i]
		if i + b <= a:
			if s[i] == '1' and c % 2 == 0 or (s[i] == '0' and c % 2 == 1):
				c = c + 1
				li[i + b] = li[i + b] - 1
			ans = ans + '0'
		elif c % 2 == 0:
			ans = ans + s[i]
		elif s[i] == '0':
			ans = ans + '1'
		else:
			ans = ans + '0'
	print(ans)


from math import inf
from collections import *
import math, os, sys, heapq, bisect, random, threading
from functools import lru_cache
from itertools import *
import sys

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def inpu():
	return int(inp())

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())
(M, M1) = (1000000007, 998244353)

def main():
	how_much_noob_I_am = 1
	how_much_noob_I_am = inpu()
	for _ in range(how_much_noob_I_am):
		(n, k) = sep()
		s = list(inp())
		res = []
		for i in range(len(s)):
			ind = bisect.bisect_left(res, i - k + 1)
			tot = len(res) - ind
			if tot % 2 != 0:
				s[i] = str(int(s[i]) ^ 1)
			if i + k - 1 < n:
				if s[i] == '1':
					s[i] = '0'
					res.append(i)
		print(''.join(s))
main()


iter = int(input())
for z in range(iter):
	(n, k) = list(map(int, input().split(' ')))
	s = input()
	pre = [0] * n
	cum = 0
	ans = '0' * (n - k + 1)
	for i in range(n - k + 1):
		if cum == 0 and s[i] == '1' or (cum == 1 and s[i] == '0'):
			pre[i] ^= 1
			pre[i + k - 1] ^= 1
		cum ^= pre[i]
	for i in range(n - k + 1, n):
		if cum == 1:
			if s[i] == '1':
				ans += '0'
			else:
				ans += '1'
		else:
			ans += s[i]
		cum ^= pre[i]
	print(ans)


from collections import deque
T = int(input())

def solve(lst, N, K):
	f = 0
	Q = deque()
	for i in range(N - K + 1):
		if Q and Q[0] < i:
			Q.popleft()
		if len(Q) % 2 == 1:
			num = 1 - lst[i]
		else:
			num = lst[i]
		if num == 1:
			lst[i] = 0
			Q.append(i + K - 1)
		else:
			lst[i] = num
	for i in range(N - K + 1, N):
		if Q and Q[0] < i:
			Q.popleft()
		if len(Q) % 2 == 1:
			lst[i] = 1 - lst[i]
	return ''.join([str(x) for x in lst])
	return ''.join([str(x) for x in lst])
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	st = [int(x) for x in list(input())]
	print(solve(st, N, K))


def display(arr):
	for i in arr:
		print(i, end='')
	print()

def k_flip():
	(n, k) = map(int, input().split())
	string = list(input())
	temp = 0
	zeroes = list(map(int, list('0' * (2 * n + 1))))
	for i in range(n - k + 1):
		if (int(string[i]) + temp) % 2 == 1:
			temp += 1
			zeroes[i + k - 1] = 1
		temp -= zeroes[i]
		string[i] = 0
	for i in range(n - k + 1, n):
		string[i] = (int(string[i]) + temp) % 2
		temp -= zeroes[i]
	display(string)
for _ in range(int(input())):
	k_flip()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	opp = n - k + 1
	s = [0] * 100001
	a = [0] * 200001
	t = 0
	string = input()
	for i in range(1, n + 1):
		s[i] = int(string[i - 1])
	for i in range(1, n - k + 2):
		if (s[i] + t) % 2 == 1:
			t += 1
			a[i + k - 1] = 1
		t -= a[i]
		s[i] = 32
	for i in range(n - k + 2, n + 1):
		s[i] = 32 + (s[i] + t) % 2
		t -= a[i]
	ans = ''
	for i in range(1, n + 1):
		ans += str(s[i] % 32)
	print(ans)


from collections import deque
T = int(input())
for i in range(T):
	(N, K) = [int(z) for z in input().strip().split()]
	string = list(input())
	queue = deque()
	for i in range(N - K + 1):
		if len(queue) > 0:
			ele = queue.popleft()
			if i - ele < K:
				queue.appendleft(ele)
		if len(queue) % 2 == 0 and string[i] == '1':
			string[i] = '0'
			queue.append(i)
		elif len(queue) % 2 == 1 and string[i] == '0':
			queue.append(i)
		elif len(queue) % 2 == 1 and string[i] == '1':
			string[i] = '0'
	for i in range(N - K + 1, N):
		if len(queue) > 0:
			ele = queue.popleft()
			if i - ele < K:
				queue.appendleft(ele)
		if len(queue) % 2 == 1:
			string[i] = str(1 - int(string[i]))
	print(''.join(string))


def sol():
	(n, k) = map(int, input().split())
	st = input()
	s = []
	for i in st:
		s.append(ord(i))
	a = [None] * 200001
	t = 0
	for i in range(0, 2 * n + 1):
		a[i] = 0
	for i in range(0, n - k + 1):
		if (s[i] + t) % 2 == 1:
			t += 1
			a[i + k - 1] = 1
		t -= a[i]
		s[i] = 48
	for i in range(n - k + 1, n):
		s[i] = 48 + (s[i] + t) % 2
		t -= a[i]
	for i in s:
		print(chr(i), end='')
	print()
T = int(input())
for t in range(T):
	sol()


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	(p, s) = (input(), [0] * (n + 1))
	for i in range(1, n + 1):
		s[i] = int(p[i - 1])
	(t, x) = (0, [0] * (2 * n + 1))
	for i in range(n - k + 2):
		if (t + s[i]) % 2:
			(x[i + k - 1], t) = (1, t + 1)
		t -= x[i]
		s[i] = 48
	for i in range(n - k + 2, n + 1):
		s[i] = (t + s[i]) % 2 + 48
		t -= x[i]
	for i in range(1, n + 1):
		print(chr(s[i]), end='')
	print()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	l = [val for val in s]
	arr = [0 for i in range(n + 1)]
	for i in range(n):
		if i <= n - k:
			if i == 0:
				if s[i] == '1':
					arr[i] += 1
					arr[i + k] -= 1
					l[i] = '0'
			else:
				arr[i] += arr[i - 1]
				if s[i] == '1':
					if arr[i] % 2:
						l[i] = '0'
					else:
						arr[i] += 1
						arr[i + k] -= 1
						l[i] = '0'
				elif arr[i] % 2:
					arr[i] += 1
					arr[i + k] -= 1
					l[i] = '0'
				else:
					l[i] = '0'
		else:
			arr[i] += arr[i - 1]
			if s[i] == '1' and arr[i] % 2:
				l[i] = '0'
			elif s[i] == '0' and arr[i] % 2:
				l[i] = '1'
	ans = ''
	for val in l:
		ans += val
	print(ans)


t = int(input())
while t:
	(p, q) = map(int, input().split())
	s = input()
	(s, j) = ([*s], 2 * p + 1)
	(m, check, h) = ([0] * j, 0, 1)
	while h < p - q + 2:
		if (check + int(s[h - 1])) % 2 == 1:
			check = check + 1
			m[q + h - 1] = 1
		check = check - m[h]
		s[h - 1] = 48
		h += 1
	h = p - q + 2
	while h < p + 1:
		s[h - 1] = (check + int(s[h - 1])) % 2 + 48
		check = check - m[h]
		h += 1
	print(''.join((chr(i) for i in s)))
	t -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	ans = []
	arr = [0] * (n + 1)
	c = 0
	op = 0
	for i in range(n - k + 1):
		op += 1
		f = 0
		if s[i] == '1':
			if (c - arr[i]) % 2 == 0:
				ans.append('0')
				c += 1
				f = 1
			else:
				ans.append('0')
		elif (c - arr[i]) % 2 == 1:
			ans.append('0')
			c += 1
			f = 1
		else:
			ans.append('0')
		arr[i + k] = c
	for i in range(n - k + 1, n):
		if s[i] == '1':
			if abs(arr[i] - c) % 2 == 1:
				ans.append('0')
			else:
				ans.append('1')
		elif abs(arr[i] - c) % 2 == 0:
			ans.append('0')
		else:
			ans.append('1')
	print(''.join(ans))


I = lambda : list(map(int, input().split()))
import bisect as bi
inv = lambda x: '1' if x == '0' else '0'
(t,) = I()
for i in range(t):
	(n, k) = I()
	s = input().strip()
	ops = []
	an = ''
	for i in range(n):
		flip = len(ops) - bi.bisect_right(ops, i - k)
		if i + k <= n:
			cur = ord(s[i]) - ord('0') ^ (flip % 2 != 0)
			if cur:
				ops.append(i)
			an += '0'
		else:
			an += inv(s[i]) if flip % 2 else s[i]
	print(an)


ri = lambda : int(input())
rl = lambda : list(map(int, input().split()))
rs = lambda : input()
from collections import defaultdict
import sys
sys.setrecursionlimit(100000)
t = ri()
for test in range(t):
	(n, k) = rl()
	s = list(rs())
	mx = n - k + 1
	pre = [0] * (n + 1)
	i = 0
	p = 0
	while i < n:
		pre[i] += p
		if s[i] == '0' and pre[i] % 2 or (s[i] == '1' and pre[i] % 2 == 0):
			if mx > 0 and i + k <= n:
				pre[i] += 1
				pre[i + k] -= 1
				mx -= 1
		p = pre[i]
		i += 1
	for i in range(n):
		if s[i] == '0' and pre[i] % 2:
			s[i] = '1'
		elif s[i] == '1' and pre[i] % 2:
			s[i] = '0'
	print(''.join(s))


t = int(input())
for i in range(t):
	[n, k] = list(map(int, input().split(' ')))
	arr = list(input())
	d = []
	for j in range(0, n):
		if len(d) and d[0] < j:
			d.pop(0)
			p = 0
			while True:
				if p == len(d):
					break
				if d[p] >= j:
					break
				else:
					d.pop(0)
		ch = len(d)
		if ch != 0:
			if ch % 2 != 0:
				arr[j] = str(int(not int(arr[j])))
		if j < n - k + 1:
			if arr[j] == '1':
				arr[j] = str(int(not int(arr[j])))
				d.append(j + k - 1)
	print(''.join(arr))


T = int(input())
for i in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = [0]
	tempo = input()
	for i in tempo:
		if i == '1':
			S.append(1)
		else:
			S.append(0)
	a = [0] * (2 * N)
	temp = 0
	for i in range(1, N - K + 2):
		if (S[i] + temp) % 2 == 1:
			temp += 1
			a[i + K - 1] = 1
		temp -= a[i]
		S[i] = 48
	for i in range(N - K + 2, N + 1):
		S[i] = (48 + S[i] + temp) % 2
		temp -= a[i]
	print('0' * (N - K + 1), end='')
	for i in S[N - K + 2:]:
		print(i, end='')
	print()


t = int(input())
while t:
	(n, k) = map(int, input().split())
	s = input()
	s = list('b' + s)
	a = [0] * (2 * n)
	c = 0
	for i in range(1, n - k + 2):
		if (int(s[i]) + c) % 2 == 1:
			c += 1
			a[i + k - 1] = 1
		c -= a[i]
		s[i] = 0
	for i in range(n - k + 2, n + 1):
		s[i] = 0 + (int(s[i]) + c) % 2
		c -= a[i]
	for i in range(1, n + 1):
		print(f'{s[i]}', end='', sep='')
	print()
	t -= 1


for i in range(int(input())):
	(n, k) = [int(j) for j in input().split()]
	s = [int(j) for j in input()]
	out = []
	flip = False
	next_flip = [False for j in range(n + 1)]
	for j in range(n - k + 1):
		if next_flip[j] == True:
			flip = not flip
		if not flip and s[j] == 1 or (flip and s[j] == 0):
			out.append(0)
			flip = not flip
			next_flip[j + k] = not next_flip[j + k]
		else:
			out.append(0)
	for j in range(n - k + 1, n):
		if next_flip[j] == True:
			flip = not flip
		if flip:
			if s[j] == 0:
				out.append(1)
			else:
				out.append(0)
		else:
			out.append(s[j])
	print(''.join([str(j) for j in out]))


def Solution(C, B):
	(N, K) = C
	S = [B[i] for i in range(N)]
	ans = ''
	L = [0 for x in range(N + 1)]
	v = 0
	for i in range(N):
		v += L[i]
		if v % 2 == 0:
			if S[i] == '0':
				ans += '0'
			elif S[i] == '1':
				if i < N - K + 1:
					ans += '0'
					v += 1
					L[i + K] += -1
				else:
					ans += '1'
		elif S[i] == '0':
			if i < N - K + 1:
				ans += '0'
				v += 1
				L[i + K] += -1
			else:
				ans += '1'
		elif S[i] == '1':
			ans += '0'
	return ans
for T in range(int(input())):
	C = map(int, input().split())
	B = input()
	ans = Solution(C, B)
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = [i for i in input()]
	arr = [0 for _ in range(n)]
	pre = 0
	for i in range(n - k + 1):
		if i >= k:
			pre -= arr[i - k]
		if s[i] == '1' and pre % 2 == 0 or (s[i] == '0' and pre % 2 == 1):
			arr[i] = 1
			pre += 1
	s[:n - k + 1] = ['0' for _ in range(n - k + 1)]
	for i in range(n - k + 1, n):
		if i >= k:
			pre -= arr[i - k]
		if pre % 2 == 1:
			if s[i] == '0':
				s[i] = '1'
			else:
				s[i] = '0'
	print(*s, sep='')


n_tests = int(input())
for _ in range(n_tests):
	(n, k) = map(int, input().split())
	S = int(input(), 2)
	k1 = int('1' * k, 2)
	for i in range(n - 1, k - 2, -1):
		if S >> i:
			S ^= k1 << i - k + 1
	end = bin(S)[2:]
	print('0' * (n - len(end)) + end)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	l = [int(i) for i in s]
	ob = [0 for i in range(len(l))]
	count = 0
	flips = 0
	for i in range(len(l) - k + 1):
		if i > 0:
			ob[i] += ob[i - 1]
		if l[i] == 1 and (flips - ob[i]) % 2 == 0 or (l[i] == 0 and (flips - ob[i]) % 2 != 0):
			flips += 1
			if i + k != len(l):
				ob[i + k] += 1
			count += 1
		l[i] = 0
		if count == n - k + 1:
			break
	if i == len(l) - k + 1:
		i -= 1
	for j in range(i + 1, len(l)):
		if j > 0:
			ob[j] += ob[j - 1]
		if l[j] == 1 and (flips - ob[j]) % 2 != 0:
			l[j] = 0
		elif l[j] == 0 and (flips - ob[j]) % 2 != 0:
			l[j] = 1
	ans = ''
	for i in l:
		ans += str(i)
	print(ans)