You are given a binary string S.

In one second, the following scenario happens simultaneously and independently for all the bits which are set to 1 in the string:

Change the bit from 1 to 0.
If the left neighbour exists and is 0, change it to 1.
If the right neighbour exists and is 0, change it to 1.

For example, if S = 010 initially, then after 1 second, S = 101 (the 1 bit and both its neighbours were changed). After another second, S = 010. Here, the first and the last bit were changed to 0 because earlier they were 1. The middle bit was changed because it was 0 earlier and it was a neighbour of a 1 bit.

Find out the string S after K seconds.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains two space-separated integers N and K — the length of string S and the number of seconds.
- The next line describes the string S.

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

For each test case, output the string S after exactly K seconds.

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

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 10^{5}$
$1 ≤ K ≤ 10^{9}$
- The sum of $N$ over all test cases won't exceed $10^{6}$.
$S$ can only contain the characters $0$ or $1$.

----- Sample Input 1 ------ 
3
3 1
101
5 2
10001
14 3
10011010111000
----- Sample Output 1 ------ 
010
10101
01100101010101
----- explanation 1 ------ 
Test case $1$: The middle bit is changed to $1$ since it had a neighbouring set bit (in this case both left and right) and both the set bits are changed to $0$. Hence, after one second, it is $101$.

Test case $2$: After first second, the string $S$ will be $01010$. After another second , the string becomes $10101$.

Difficulty: HARD
Tags: Constructive algorithms

Ad-hoc

Starter code:

Solutions:
from collections import deque
for _ in range(int(input())):
	(N, K) = list(map(int, input().split()))
	visited1 = [False] * N
	visited0 = [False] * N
	S = input()
	q0 = deque()
	q1 = deque()
	for i in range(N):
		if S[i] == '1':
			q1.append(i)
			visited1[i] = True
		else:
			q0.append(i)
			visited0[i] = True
	nrstones = [1] * N
	nrstzeroes = [1] * N
	if len(q0) == 0 or len(q1) == 0:
		print('0' * N)
		continue
	t = 0
	while q0:
		for i in range(len(q0)):
			x = q0.popleft()
			nrstzeroes[x] = t
			if x > 0 and visited0[x - 1] == False:
				q0.append(x - 1)
				visited0[x - 1] = True
			if x < N - 1 and visited0[x + 1] == False:
				q0.append(x + 1)
				visited0[x + 1] = True
		t += 1
	t = 0
	while q1:
		for i in range(len(q1)):
			x = q1.popleft()
			nrstones[x] = t
			if x > 0 and visited1[x - 1] == False:
				q1.append(x - 1)
				visited1[x - 1] = True
			if x < N - 1 and visited1[x + 1] == False:
				q1.append(x + 1)
				visited1[x + 1] = True
		t += 1
	s = ''
	for i in range(N):
		if S[i] == '1':
			if nrstzeroes[i] % 2 != K % 2 and K > nrstzeroes[i]:
				s += '1'
			else:
				s += '0'
		elif nrstones[i] % 2 == K % 2 and K >= nrstones[i]:
			s += '1'
		else:
			s += '0'
	print(s)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	S = list(map(int, input()))
	K -= 1
	new_S = [0] * N
	for i in range(len(S)):
		if S[i] == 1:
			new_S[i] = 0
			if i > 0 and S[i - 1] == 0:
				new_S[i - 1] = 1
			if i < N - 1 and S[i + 1] == 0:
				new_S[i + 1] = 1
	S = new_S
	if 1 not in S:
		print('0' * N)
		continue
	ones = []
	for i in range(len(S)):
		if S[i] == 1:
			ones.append(i)
	result = ''
	current_one = 0
	for i in range(N):
		diff = abs(ones[current_one] - i)
		if current_one < len(ones) - 1:
			next_diff = abs(ones[current_one + 1] - i)
			if next_diff <= diff:
				diff = next_diff
				current_one += 1
		if diff % 2 == K % 2 and diff <= K:
			result += '1'
		else:
			result += '0'
	print(result)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	t = [0] * n
	for i in range(n):
		if s[i] == '0':
			continue
		t[i] = 0
		if i > 0 and s[i - 1] == '0':
			t[i - 1] = 1
		if i + 1 < n and s[i + 1] == '0':
			t[i + 1] = 1
	k -= 1
	dist = [n + 1] * n
	prv = -1
	for i in range(n):
		if t[i] == 1:
			prv = i
		if prv != -1:
			dist[i] = i - prv
	prv = -1
	for i in reversed(range(n)):
		if t[i] == 1:
			prv = i
		if prv != -1:
			dist[i] = min(dist[i], prv - i)
	ans = ''
	for i in range(n):
		first = dist[i]
		if first == n + 1 or first > k:
			ans += '0'
		elif (k - first) % 2 == 0:
			ans += '1'
		else:
			ans += '0'
	print(ans)


def do_first_step(array):
	new_array = [0] * len(array)
	for (k, v) in enumerate(array):
		if v == 1:
			if k - 1 >= 0 and array[k - 1] == 0:
				new_array[k - 1] = 1
			if k + 1 < len(array) and array[k + 1] == 0:
				new_array[k + 1] = 1
	return new_array

def do_age(array, age):
	array = do_first_step(array)
	age -= 1
	if age == 0:
		return array
	new_array = [0] * len(array)
	distances = [10 ** 8] * len(array)
	cur_distance = 10 ** 8
	for (k, el) in enumerate(array):
		if el == 1:
			cur_distance = 0
		else:
			cur_distance += 1
		distances[k] = min(distances[k], cur_distance)
	cur_distance = 10 ** 8
	for (k, el) in reversed(list(enumerate(array))):
		if el == 1:
			cur_distance = 0
		else:
			cur_distance += 1
		distances[k] = min(distances[k], cur_distance)
	for (k, dist) in enumerate(distances):
		if age < dist:
			new_array[k] = 0
		else:
			new_array[k] = 1 if (age - dist) % 2 == 0 else 0
	return new_array
for _ in range(int(input())):
	(_, age) = map(int, input().split())
	array = list(map(int, input()))
	array = do_age(array, age)
	print(''.join(map(str, array)))


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = input()
	dp = [10 ** 7 for i in range(n)]
	if l[0] == '1':
		dp[0] = 0
	for i in range(1, n):
		if l[i] == '0':
			dp[i] = dp[i - 1] + 1
		else:
			dp[i] = 0
	d = [10 ** 7 for i in range(n)]
	if l[n - 1] == '1':
		d[n - 1] = 0
	else:
		d[n - 1] = dp[n - 1]
	for i in range(n - 2, -1, -1):
		if l[i] == '0':
			d[i] = min(dp[i], d[i + 1] + 1)
		else:
			d[i] = 0
	dp1 = [10 ** 7 for i in range(n)]
	if l[0] == '0':
		dp1[0] = 0
	for i in range(1, n):
		if l[i] == '1':
			dp1[i] = dp1[i - 1] + 1
		else:
			dp1[i] = 0
	d1 = [10 ** 7 for i in range(n)]
	if l[n - 1] == '0':
		d1[n - 1] = 0
	else:
		d1[n - 1] = dp1[n - 1]
	for i in range(n - 2, -1, -1):
		if l[i] == '1':
			d1[i] = min(dp1[i], d1[i + 1] + 1)
		else:
			d1[i] = 0
	if k % 2 == 0:
		for i in range(n):
			if l[i] == '1':
				if d1[i] > k:
					print(0, end='')
				elif d1[i] % 2 == 0:
					print(1 - int(l[i]), end='')
				elif d1[i] % 2 != 0:
					print(int(l[i]), end='')
			if l[i] == '0':
				if d[i] > k:
					print(0, end='')
				elif d[i] % 2 == 0:
					print(1 - int(l[i]), end='')
				elif d[i] % 2 != 0:
					print(int(l[i]), end='')
	if k % 2 == 1:
		for i in range(n):
			if l[i] == '1':
				if d1[i] > k:
					print(0, end='')
				elif d1[i] % 2 == 0:
					print(int(l[i]), end='')
				elif d1[i] % 2 != 0:
					print(1 - int(l[i]), end='')
			if l[i] == '0':
				if d[i] > k:
					print(0, end='')
				elif d[i] % 2 == 0:
					print(int(l[i]), end='')
				elif d[i] % 2 != 0:
					print(1 - int(l[i]), end='')
	print(' ')


import time
import sys
import math

def get_primes(n):
	sieve = [True] * n
	for i in range(3, int(n ** 0.5) + 1, 2):
		if sieve[i]:
			sieve[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
	return [2] + [i for i in range(3, n, 2) if sieve[i]]
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from functools import reduce

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))
input = sys.stdin.readline
(mod, infi) = (1000000007, sys.maxsize)
from collections import deque, Counter, defaultdict as dd
from heapq import heappop, heappush, heapify
from itertools import accumulate
from functools import lru_cache, reduce
from operator import mul, add, sub, truediv, floordiv, lt, le, eq, ne, gt, xor, concat, getitem, pow, lshift
inty = lambda : int(input())
stringy = lambda : input().strip()
normal = lambda : input().split()
mappy = lambda : map(int, input().strip().split())
fmappy = lambda : map(float, input().strip().split())
listy = lambda : list(map(int, input().strip().split()))
tick = lambda : time.perf_counter()
logg = lambda a, b: math.log2(a) / math.log2(b)
acc = lambda x: list(accumulate(x))
sign = lambda x, y: x >= 0 and y >= 0 or (x < 0 and y < 0)

def flipper(s, n):
	new = ['0'] * n
	for i in range(n):
		if s[i] == '1':
			if i - 1 >= 0:
				new[i - 1] = str(int(s[i - 1]) ^ 1)
			if i + 1 < n:
				new[i + 1] = str(int(s[i + 1]) ^ 1)
	return new
T = inty()
for _ in range(T):
	(n, k) = mappy()
	s = [i for i in stringy()]
	s = flipper(s, n)
	k -= 1
	turn = [n + 1] * n
	prev = -1
	for i in range(n):
		if s[i] == '1':
			prev = i
		if prev != -1:
			turn[i] = i - prev
	prev = -1
	for i in range(n - 1, -1, -1):
		if s[i] == '1':
			prev = i
		if prev != -1:
			turn[i] = min(turn[i], prev - i)
	res = ['0'] * n
	for i in range(n):
		if turn[i] != n + 1 and turn[i] <= k:
			l = k - turn[i]
			if l & 1:
				res[i] = '0'
			else:
				res[i] = '1'
	print(''.join(res))


import collections
import heapq
import sys
import math
import itertools
import bisect
from io import BytesIO, IOBase
import os

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

def inlsts():
	return [int(i) for i in sys.stdin.readline().split()]

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

def instr():
	return sys.stdin.readline().strip()

def words():
	return [i for i in sys.stdin.readline().strip().split()]

def chars():
	return [i for i in sys.stdin.readline().strip()]

def solve():
	(n, k) = values()
	s = instr()
	t = [0] * n
	for i in range(n):
		if s[i] == '0':
			continue
		t[i] = 0
		if i + 1 < n and s[i + 1] == '0':
			t[i + 1] = 1
		if i - 1 > -1 and s[i - 1] == '0':
			t[i - 1] = 1
	prv = -1
	des = [n + 1] * n
	for i in range(n):
		if t[i] == 1:
			prv = i
		if prv != -1:
			des[i] = i - prv
	prv = -1
	for i in range(n - 1, -1, -1):
		if t[i] == 1:
			prv = i
		if prv != -1:
			des[i] = min(prv - i, des[i])
	r = ''
	k -= 1
	for i in range(n):
		if des[i] > k or des[i] == n + 1:
			r += '0'
		elif (k - des[i]) % 2 == 0:
			r += '1'
		else:
			r += '0'
	print(r)
for i in range(inp()):
	solve()


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	r = input().rstrip()
	ok = [i for i in r]
	for i in range(n):
		if ok[i] == '0' and (i != 0 and ok[i - 1] == '1' or (i != n - 1 and ok[i + 1] == '1')):
			ok[i] = '2'
	for i in range(n):
		if ok[i] == '1':
			ok[i] = '0'
		if ok[i] == '2':
			ok[i] = '1'
	left = [-1 for i in range(n)]
	right = [-1 for i in range(n)]
	for i in range(n):
		if ok[i] == '1':
			left[i] = i
		elif i:
			left[i] = left[i - 1]
	for i in range(n - 1, -1, -1):
		if ok[i] == '1':
			right[i] = i
		elif i != n - 1:
			right[i] = right[i + 1]
	k -= 1
	if k:
		for i in range(n):
			if ok[i] == '1':
				if k % 2:
					ok[i] = '0'
			else:
				(d1, d2) = (-1, -1)
				if left[i] != -1:
					d1 = abs(i - left[i])
				if right[i] != -1:
					d2 = abs(i - right[i])
				if d1 == -1 and d2 == -1:
					continue
				elif d1 != -1 and d2 != -1:
					d1 = min(d1, d2)
				elif d1 == -1:
					d1 = d2
				else:
					pass
				if d1 > k:
					pass
				elif (d1 - k) % 2 == 0:
					ok[i] = '1'
	res = ''.join(ok)
	print(res)


t = int(input())
for T in range(t):
	(n, k) = map(int, input().split())
	s = list(input())
	k -= 1
	for i in range(n):
		if s[i] == '1':
			s[i] = '-1'
			if i > 0 and s[i - 1] == '0':
				s[i - 1] = '2'
			if i < n - 1 and s[i + 1] == '0':
				s[i + 1] = '2'
	for i in range(n):
		if s[i] == '-1':
			s[i] = '0'
		elif s[i] == '2':
			s[i] = '1'
	m = -1
	left = [0 for i in range(n)]
	right = [0 for i in range(n)]
	index = [0 for i in range(n)]
	for i in range(0, n):
		if s[i] == '1':
			m = i
		elif m != -1:
			left[i] = i - m
		else:
			left[i] = -1
	m = -1
	for i in range(n - 1, -1, -1):
		if s[i] == '1':
			m = i
		elif m != -1:
			right[i] = m - i
		else:
			right[i] = -1
	for i in range(n):
		if s[i] != '1':
			if right[i] != -1 and left[i] != -1:
				if right[i] < left[i]:
					index[i] = right[i]
				else:
					index[i] = left[i]
			elif right[i] != -1:
				index[i] = right[i]
			else:
				index[i] = left[i]
	for i in range(n):
		if k < index[i]:
			print(s[i], end='')
		elif index[i] == -1:
			print(s[i], end='')
		elif index[i] == 0:
			if k % 2 == 1:
				if s[i] == '1':
					print(0, end='')
				else:
					print(1, end='')
			else:
				print(s[i], end='')
		elif index[i] != 0 and (k - 1 - index[i]) % 2 == 0:
			print(s[i], end='')
		elif s[i] == '1':
			print(0, end='')
		else:
			print(1, end='')
	print()


for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = input()
	a = list(a)
	t = [0] * n
	for i in range(n):
		if a[i] == '0':
			if i > 0:
				if i == n - 1:
					if a[n - 2] == '1':
						t[i] = '1'
				elif a[i - 1] == '1' or a[i + 1] == '1':
					t[i] = '1'
				else:
					t[i] = '0'
			elif n > 1:
				if a[i + 1] == '1':
					t[i] = '1'
		else:
			t[i] = '0'
	a = t
	k = k - 1
	kp = []
	ks = []
	mark = 1000000007
	for i in range(n):
		if a[i] == '1':
			mark = i + 1
			kp.append(mark)
		else:
			kp.append(mark)
	mark = 1000000007
	for i in reversed(range(n)):
		if a[i] == '1':
			mark = i + 1
			ks.append(mark)
		else:
			ks.append(mark)
	ks = ks[::-1]
	s = ''
	for i in range(n):
		(p1, s1) = (abs(kp[i] - (i + 1)), abs(ks[i] - (i + 1)))
		x = min(p1, s1)
		if x == n + 1:
			s += '0'
		elif (x + k) % 2 == 0 and x <= k:
			s += '1'
		else:
			s += '0'
	print(s)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	s = input()
	t = [0] * N
	for i in range(N):
		if s[i] == '0':
			continue
		t[i] = 0
		if i > 0 and s[i - 1] == '0':
			t[i - 1] = 1
		if i + 1 < N and s[i + 1] == '0':
			t[i + 1] = 1
	K -= 1
	dist = [N + 1] * N
	pre = -1
	for i in range(N):
		if t[i] == 1:
			pre = i
		if pre != -1:
			dist[i] = i - pre
	pre = -1
	for i in reversed(range(N)):
		if t[i] == 1:
			pre = i
		if pre != -1:
			dist[i] = min(dist[i], pre - i)
	res = ''
	for i in range(N):
		b = dist[i]
		if b == N + 1 or b > K:
			res += '0'
		elif (K - b) % 2 == 0:
			res += '1'
		else:
			res += '0'
	print(res)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	t = [0] * n
	for i in range(n):
		if s[i] == '0':
			continue
		if i > 0 and s[i - 1] == '0':
			t[i - 1] = 1
		if i + 1 < n and s[i + 1] == '0':
			t[i + 1] = 1
	k -= 1
	(waktu, sebelum) = ([n + 1] * n, -1)
	for i in range(n):
		if t[i]:
			sebelum = i
		if sebelum != -1:
			waktu[i] = min(waktu[i], i - sebelum)
	sebelum = -1
	for i in reversed(range(n)):
		if t[i]:
			sebelum = i
		if sebelum != -1:
			waktu[i] = min(waktu[i], sebelum - i)
	ans = ''
	for i in range(n):
		ans += '0' if waktu[i] > k or waktu[i] == n + 1 or k - waktu[i] & 1 else '1'
	print(ans)


tests = int(input())
for i in range(tests):
	(n, k) = map(int, input().split())
	string = input()
	if n == 1:
		print('0')
	elif string.count('0') == 0 or string.count('1') == 0:
		print('0' * n)
	else:
		temp = ''
		for j in range(n):
			if string[j] == '1':
				temp += '0'
			elif j - 1 >= 0 and string[j - 1] == '1':
				temp += '1'
			elif j + 1 < n and string[j + 1] == '1':
				temp += '1'
			else:
				temp += '0'
		string = temp
		k -= 1
		if k > 0:
			dist = [n + 1] * n
			previous = -1
			for j in range(n):
				if string[j] == '1':
					previous = j
				if previous != -1:
					dist[j] = j - previous
			previous = -1
			for j in range(n - 1, -1, -1):
				if string[j] == '1':
					previous = j
				if previous != -1:
					dist[j] = min(dist[j], previous - j)
			ans = ''
			for j in range(n):
				subs = dist[j]
				if subs > 0:
					subs -= 1
				remaining_secs = k - subs
				if remaining_secs >= 0:
					if remaining_secs % 2 == 0:
						ans += string[j]
					elif string[j] == '1':
						ans += '0'
					else:
						ans += '1'
				else:
					ans += '0'
			print(ans)
		else:
			print(string)


tests = int(input())
for i in range(tests):
	(n, k) = map(int, input().split())
	string = input()
	if n == 1:
		print('0')
	elif string.count('0') == 0 or string.count('1') == 0:
		print('0' * n)
	else:
		temp = ''
		for j in range(n):
			if string[j] == '1':
				temp += '0'
			elif j - 1 >= 0 and string[j - 1] == '1':
				temp += '1'
			elif j + 1 < n and string[j + 1] == '1':
				temp += '1'
			else:
				temp += '0'
		string = temp
		k -= 1
		if k > 0:
			left_one_dist = []
			right_one_dist = []
			left_one = -1
			right_one = -1
			for j in range(n):
				if string[j] == '1':
					left_one = 0
				elif left_one != -1:
					left_one += 1
				left_one_dist.append(left_one)
			for j in range(n - 1, -1, -1):
				if string[j] == '1':
					right_one = 0
				elif right_one != -1:
					right_one += 1
				right_one_dist.append(right_one)
			right_one_dist = right_one_dist[::-1]
			ans = ''
			for j in range(n):
				if min(right_one_dist[j], left_one_dist[j]) == -1:
					subs = max(right_one_dist[j], left_one_dist[j])
				else:
					subs = min(right_one_dist[j], left_one_dist[j])
				if subs > 0:
					subs -= 1
				remaining_secs = k - subs
				if remaining_secs >= 0:
					if remaining_secs % 2 == 0:
						ans += string[j]
					elif string[j] == '1':
						ans += '0'
					else:
						ans += '1'
				else:
					ans += '0'
			print(ans)
		else:
			print(string)


def give(ans, k):
	if k % 2 == 0:
		return 1 if ans % 2 == 0 and ans <= k else 0
	else:
		return 1 if ans % 2 == 1 and ans <= k else 0
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = [i for i in input()]
	if len(s) == 1:
		print('0') if k >= 1 else print(s[0])
		continue
	(ini, fin) = (['inf'] * n, ['inf'] * n)
	m = float('inf')
	k -= 1
	duplicate = s.copy()
	for i in range(n):
		if i == 0:
			if s[i] == '1':
				duplicate[i] = '0'
			elif s[i + 1] == '1':
				duplicate[i] = '1'
			continue
		if i == n - 1:
			if s[i] == '1':
				duplicate[i] = '0'
			elif s[i - 1] == '1':
				duplicate[i] = '1'
			continue
		if s[i] == '1':
			duplicate[i] = '0'
		elif s[i - 1] == '1' or s[i + 1] == '1':
			duplicate[i] = '1'
	s = duplicate.copy()
	for i in range(n):
		if s[i] == '1':
			m = 0
		else:
			m += 1
		ini[i] = m
	for i in range(n - 1, -1, -1):
		if s[i] == '1':
			m = 0
		else:
			m += 1
		fin[i] = m
	ans = [None] * n
	for i in range(n):
		ans[i] = min(ini[i], fin[i])
	if ans[0] == float('inf') or ans[-1] == float('inf'):
		sol = [0] * n
		print(*sol, sep='')
		continue
	elif k % 2:
		sol = [give(ans[i], k) for i in range(n)]
	else:
		sol = [give(ans[i], k) for i in range(n)]
	print(*sol, sep='')


import math
from functools import reduce

def read(func=str, sep=None):
	return list(map(func, input().split(sep)))

def read_ints(sep=None):
	return read(func=int, sep=sep)

def read_int():
	return int(input())

def print_array(arr, sep=' '):
	print(sep.join(map(str, arr)))

def setbitcount(num):
	bits = 0
	while num:
		bits += num & 1
		num >>= 1
	return bits
test_cases = read_int()
for _ in range(test_cases):
	(n, k) = read_ints()
	s = list(input())
	pending_up = set()
	should_not_up = set()
	i = 0
	while i < n:
		item = s[i]
		if item == '1':
			s[i] = '0'
			pending_up.add(i - 1)
			pending_up.add(i + 1)
			should_not_up.add(i)
		else:
			pass
		i += 1
	for item in pending_up - should_not_up:
		if 0 <= item < n:
			s[item] = '1'
	nearest = [100000000.0] * n
	i = 0
	last_1 = None
	while i < n:
		item = s[i]
		if item == '1':
			last_1 = i
			nearest[i] = 0
		if item == '0':
			nearest[i] = min(i - last_1, nearest[i]) if last_1 is not None else nearest[i]
		i += 1
	i = n - 1
	last_1 = None
	while i >= 0:
		item = s[i]
		if item == '1':
			last_1 = i
			nearest[i] = 0
		if item == '0':
			nearest[i] = min(last_1 - i, nearest[i]) if last_1 is not None else nearest[i]
		i -= 1
	if nearest[0] == 100000000.0:
		print('0' * n)
	else:
		out = [''] * n
		i = 0
		while i < n:
			item = s[i]
			out[i] = str(int((k - nearest[i]) % 2)) if nearest[i] < k else '0'
			i += 1
		print(''.join(out))


from bisect import *
from heapq import *
from math import *
from collections import defaultdict as ddc
from collections import Counter
from functools import *
from itertools import *
from sys import setrecursionlimit

def intin():
	return int(input())

def mapin():
	return map(int, input().split())

def strin():
	return input().split()
INF = 10 ** 20
mod = 1000000007

def hashit(arr, size, mod=10 ** 9 + 7):
	if not size:
		return
	(mul, hashh, div) = (256, 0, (1 << 8 * size - 8) % mod)
	C = defaultdict(list)
	for i in range(size):
		hashh = (mul * hashh + arr[i]) % mod
	C[hashh].append(0)
	for i in range(len(arr) - size):
		hashh = (mul * (hashh - arr[i] * div) + arr[i + size]) % mod
		C[hashh].append(i + 1)
	return C

def LIS(arr, n):
	dp = [10 ** 9] * (n + 1)
	for ele in arr:
		dp[bisect_left(dp, ele)] = ele
	return bisect_left(dp, 10 ** 9)

def exponentiation(bas, exp, mod=10 ** 9 + 7):
	t = 1
	while exp > 0:
		if exp % 2 != 0:
			t = t * bas % mod
		bas = bas * bas % mod
		exp //= 2
	return t % mod

def MOD(p, q=1, mod=1000000007):
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p
yes = 'YES'
no = 'NO'
even = 'EVEN'
odd = 'ODD'

def graphin(n):
	zz = defaultdict(set)
	for i in range(n - 1):
		(a, b) = mapin()
		zz[a].add(b)
		zz[b].add(a)
	return zz

def process(arr, n, k):
	ans = ['1'] * n
	for i in range(n):
		if arr[i] == '0' and (i > 0 and arr[i - 1] == '1' or (i < n - 1 and arr[i + 1] == '1')):
			arr[i] = '2'
	for i in range(n):
		if arr[i] == '2':
			arr[i] = '1'
		elif arr[i] == '1':
			arr[i] = '0'
	k -= 1
	l = -1
	r = 0
	for i in range(n):
		if i >= r:
			r += 1
			while r < n and arr[r] == '0':
				r += 1
		if arr[i] == '1':
			if k % 2:
				arr[i] = '0'
			l = i
		else:
			if l == -1 and r == n:
				break
			elif l == -1:
				limit = r - i
			elif r == n:
				limit = i - l
			else:
				limit = min(i - l, r - i)
			if arr[i] == '1':
				l = i
			if limit <= k and k % 2 == limit % 2:
				arr[i] = '1'
			else:
				arr[i] = '0'
	return ''.join(arr)

def main():
	for _ in range(int(input())):
		(n, k) = mapin()
		arr = list(input())
		print(process(arr, n, k))
main()


for _ in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	s = input()
	arr = [0] * 100001
	k -= 1
	s = '.' + s + '.'
	temp = list(s)
	for i in range(1, n + 1):
		if s[i] == '1':
			temp[i] = '0'
			if s[i - 1] == '0':
				temp[i - 1] = '1'
			if s[i + 1] == '0':
				temp[i + 1] = '1'
	s = ''.join(temp[1:n + 1])
	x = 2 ** 32 - 1
	for j in range(0, n):
		if s[j] == '1':
			x = 0
		arr[j] = x
		x += 1
	x = 2 ** 32 - 1
	for i in range(n - 1, -1, -1):
		if s[i] == '1':
			x = 0
		arr[i] = min(arr[i], x)
		x += 1
	ans = ''
	for i in range(n):
		if k < arr[i]:
			ans += '0'
		elif (k - arr[i]) % 2 == 0:
			ans += '1'
		else:
			ans += '0'
	print(ans)


import sys
import math
from collections import defaultdict
from itertools import permutations
from collections import deque

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

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

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

def multiple():
	return [int(x) for x in sys.stdin.readline().split()]

def string():
	return sys.stdin.readline().strip()
t = sin()
for _ in range(t):
	(n, k) = multiple()
	s = string()
	one = -1
	temp = [0] * n
	if '1' not in s:
		print(s)
		continue
	if '0' not in s:
		if k >= 1:
			print('0' * n)
		continue
	for i in range(n):
		if s[i] == '1':
			one = i
		elif one != -1:
			temp[i] = i - one
	one = 0
	for i in range(n - 1, -1, -1):
		if s[i] == '1':
			one = i
		elif not temp[i]:
			temp[i] = abs(i - one)
		else:
			temp[i] = min(temp[i], abs(i - one))
	zero = -1
	for i in range(n):
		if s[i] == '0':
			zero = i
		elif zero != -1:
			temp[i] = i - zero
	zero = 0
	for i in range(n - 1, -1, -1):
		if s[i] == '0':
			zero = i
		elif not temp[i]:
			temp[i] = abs(i - zero)
		else:
			temp[i] = min(temp[i], abs(i - zero))
	for i in range(n):
		temp[i] = max(temp[i], 1)
	ans = []
	for i in range(n):
		if k < temp[i]:
			if s[i] == '1':
				if k >= 1:
					ans.append('0')
				else:
					ans.append('1')
			else:
				ans.append(s[i])
			continue
		x = k - temp[i]
		if x % 2:
			if s[i] == '1':
				ans.append('1')
			else:
				ans.append('0')
		elif s[i] == '0':
			ans.append('1')
		else:
			ans.append('0')
	print(''.join(ans))


from collections import defaultdict
dic = defaultdict(int)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	string = list('_' + input() + '_')
	k -= 1
	copy_string = list(string)
	for i in range(1, n + 1):
		if string[i] == '1':
			copy_string[i] = '0'
			if string[i - 1] == '0':
				copy_string[i - 1] = '1'
			if string[i + 1] == '0':
				copy_string[i + 1] = '1'
	string = copy_string[1:n + 1]
	const = 31474836470
	for i in range(n):
		if string[i] == '1':
			const = 0
		dic[i] = const
		const += 1
	const = 31474836470
	for i in range(n - 1, -1, -1):
		if string[i] == '1':
			const = 0
		dic[i] = min(dic[i], const)
		const += 1
	for i in range(n):
		print((0, 1 - (k - dic[i]) % 2)[not k < dic[i]], end='')
	print()


import sys
a = [0] * 100001
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	k -= 1
	s = '.' + s + '.'
	t = list(s)
	for j in range(1, n + 1):
		if s[j] == '1':
			t[j] = '0'
			if s[j - 1] == '0':
				t[j - 1] = '1'
			if s[j + 1] == '0':
				t[j + 1] = '1'
	t = ''.join(t)
	s = t[1:n + 1]
	x = sys.maxsize
	for i in range(n):
		x += 1
		if s[i] == '1':
			x = 0
		a[i] = x
	x = sys.maxsize
	for i in range(n - 1, -1, -1):
		x += 1
		if s[i] == '1':
			x = 0
		a[i] = min(a[i], x)
	ans = ''
	for i in range(n):
		if k < a[i]:
			ans += '0'
		elif (k - a[i]) % 2 == 0:
			ans += '1'
		else:
			ans += '0'
	print(ans)


t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	s1 = input()
	s = [i for i in s1]
	b = [i for i in s]
	a = [0 for i in range(n)]
	for i in range(n):
		if s[i] == '1':
			b[i] = '0'
			if i != 0 and s[i - 1] == '0':
				b[i - 1] = '1'
			if i != n - 1 and s[i + 1] == '0':
				b[i + 1] = '1'
	k -= 1
	s = [i for i in b]
	j = 9876543211
	for i in range(n):
		if s[i] == '1':
			j = 0
		a[i] = j
		j += 1
	j = 9876543211
	for i in range(n - 1, -1, -1):
		if s[i] == '1':
			j = 0
		a[i] = min(j, a[i])
		j += 1
	for i in range(n):
		if k < a[i]:
			print(0, end='')
		elif (k - a[i]) % 2 != 0:
			print(0, end='')
		else:
			print(1, end='')
	print()


import random
import math
from collections import defaultdict, Counter, deque, OrderedDict
from functools import lru_cache
import bisect
import heapq
import sys
input = lambda : sys.stdin.readline().strip()

class SegmentTree:

	def __init__(self, arr, func=lambda x, y: x + y, defaultvalue=0):
		self.n = len(arr)
		self.segmentTree = [0] * self.n + arr
		self.func = func
		self.defaultvalue = defaultvalue
		self.buildSegmentTree(arr)

	def buildSegmentTree(self, arr):
		for i in range(self.n - 1, 0, -1):
			self.segmentTree[i] = self.func(self.segmentTree[2 * i], self.segmentTree[2 * i + 1])

	def query(self, l, r):
		l += self.n
		r += self.n
		res = self.defaultvalue
		while l < r:
			if l & 1:
				res = self.func(res, self.segmentTree[l])
				l += 1
			l >>= 1
			if r & 1:
				r -= 1
				res = self.func(res, self.segmentTree[r])
			r >>= 1
		return res

	def update(self, i, value):
		i += self.n
		self.segmentTree[i] = value
		while i > 1:
			i >>= 1
			self.segmentTree[i] = self.func(self.segmentTree[2 * i], self.segmentTree[2 * i + 1])

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 case(t):
	print('Case #{}:'.format(t), end=' ')
RANDOM = random.randrange(2 ** 62)

def Wrapper(x):
	return x ^ RANDOM

def get(og, k):
	n = len(og)
	dp = og[:]
	last1 = math.inf
	for i in range(n):
		if last1 <= k and og[i] == '0':
			if last1 % 2 == 0:
				dp[i] = '1'
		if og[i] == '1':
			last1 = 0
		last1 += 1
	last1 = math.inf
	for i in range(n - 1, -1, -1):
		if last1 <= k and og[i] == '0':
			if last1 % 2 == 0:
				dp[i] = '1'
		if og[i] == '1':
			last1 = 0
		last1 += 1
	return ''.join(dp)

def solve():
	(n, k) = map(int, input().split())
	s = input()
	og = list(s)
	for i in range(n):
		if s[i] == '1':
			og[i] = '0'
			if i > 0 and s[i - 1] == '0':
				og[i - 1] = '1'
			if i < n - 1 and s[i + 1] == '0':
				og[i + 1] = '1'
	k -= 1
	s = ''.join(og)
	if k % 2 == 1:
		for i in range(n):
			if s[i] == '1':
				og[i] = '0'
				if i > 0 and s[i - 1] == '0':
					og[i - 1] = '1'
				if i < n - 1 and s[i + 1] == '0':
					og[i + 1] = '1'
		k -= 1
	ans = []
	l = 0
	zc = 0
	start = False
	for i in range(n):
		if og[i] == '1':
			if zc != 0 and zc % 2 == 0 and start:
				mid = i - zc // 2
				ans.append(get(og[l:mid], k))
				l = mid
			start = True
			zc = 0
		else:
			zc += 1
	ans.append(get(og[l:], k))
	print(''.join(ans))
for t in range(int(input())):
	solve()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input().strip()
	temp = ''
	dp = [-1 for i in range(n)]
	lastZero = -1
	lastOne = -1
	for i in range(n):
		if s[i] == '0':
			if lastOne != -1:
				dp[i] = abs(lastOne - i)
			lastZero = i
		else:
			if lastZero != -1:
				dp[i] = abs(lastZero - i)
			lastOne = i
	lastZero = -1
	lastOne = -1
	for i in range(n - 1, -1, -1):
		if s[i] == '0':
			if lastOne != -1:
				if dp[i] == -1:
					dp[i] = abs(lastOne - i)
				else:
					dp[i] = min(dp[i], abs(lastOne - i))
			lastZero = i
		else:
			if lastZero != -1:
				if dp[i] == -1:
					dp[i] = abs(lastZero - i)
				else:
					dp[i] = min(dp[i], abs(lastZero - i))
			lastOne = i
	temp = ''
	for i in range(n):
		if dp[i] == 1:
			if k % 2 != 0:
				if s[i] == '0':
					temp += '1'
				else:
					temp += '0'
			else:
				temp += s[i]
		elif dp[i] == -1:
			temp += '0'
		elif dp[i] <= k:
			t = k - dp[i]
			if t % 2 == 0:
				if s[i] == '0':
					temp += '1'
				else:
					temp += '0'
			else:
				temp += s[i]
		else:
			temp += '0'
	print(temp)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	Q = input()
	k -= 1
	a = [0] * n
	string = ['0'] * n
	for i in range(n):
		if Q[i] == '1':
			string[i] = '0'
			if i > 0 and Q[i - 1] == '0':
				string[i - 1] = '1'
			if i < n - 1 and Q[i + 1] == '0':
				string[i + 1] = '1'
	Q = string[:]
	i = 0
	x = 2147483647
	while i < n:
		if Q[i] == '1':
			x = 0
		a[i] = x
		x += 1
		i += 1
	i = n - 1
	x = 2147483647
	while i > -1:
		if Q[i] == '1':
			x = 0
		a[i] = min(a[i], x)
		i -= 1
		x += 1
	for i in range(n):
		if k < a[i]:
			print('0', end='')
		elif (k - a[i]) % 2 == 0:
			print('1', end='')
		else:
			print('0', end='')
	print()


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)

def change(s):
	l = list(s)
	n = len(l)
	for i in range(n):
		if s[i] == '1':
			l[i] = '0'
			if i >= 1 and s[i - 1] == '0':
				l[i - 1] = '1'
			if i + 1 < n and s[i + 1] == '0':
				l[i + 1] = '1'
	return l
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	s = input()
	l1 = change(list(s))
	s = ''.join(l1)
	k -= 1
	if k == 0:
		print(''.join(l1))
		continue
	l = []
	for i in range(n):
		if s[i] == '1':
			l.append(i)
	l = [-10 ** 10] + l + [10 ** 10]
	for i in range(len(l) - 1):
		ind1 = l[i]
		ind2 = l[i + 1]
		zer = ind2 - ind1 - 1
		if zer % 2 == 0:
			mid1 = ind1 + zer // 2
			mid2 = ind2 - zer // 2
			mid1 = min(ind1 + k, mid1)
			mid2 = max(ind2 - k, mid2)
		else:
			mid1 = ind1 + (zer + 1) // 2
			mid2 = ind2 - (zer + 1) // 2
			mid1 = min(ind1 + k, mid1)
			mid2 = max(ind2 - k, mid2)
		c = 0
		for j in range(max(0, l[i]), min(n, mid1 + 1)):
			if c % 2 == 0:
				if k % 2 == 0:
					l1[j] = '1'
				else:
					l1[j] = '0'
			elif k % 2 == 0:
				l1[j] = '0'
			else:
				l1[j] = '1'
			c += 1
		c = 0
		for j in range(min(n - 1, l[i + 1]), max(-1, mid2 - 1), -1):
			if c % 2 == 0:
				if k % 2 == 0:
					l1[j] = '1'
				else:
					l1[j] = '0'
			elif k % 2 == 0:
				l1[j] = '0'
			else:
				l1[j] = '1'
			c += 1
	print(''.join(l1))


for _ in range(int(input())):
	a = list(map(int, input().strip().split()))
	s = input()
	if a[0] == 1:
		print(0)
	else:
		a[1] -= 1
		sl = []
		for i in range(a[0]):
			if s[i] == '1':
				sl.append(0)
			elif i == 0:
				if s[i + 1] == '1':
					sl.append(1)
				else:
					sl.append(0)
			elif i == a[0] - 1:
				if s[i - 1] == '1':
					sl.append(1)
				else:
					sl.append(0)
			elif s[i + 1] == '1' or s[i - 1] == '1':
				sl.append(1)
			else:
				sl.append(0)
		c1 = 1000001
		c2 = 1000001
		l1 = [0 for i in range(a[0])]
		l2 = [0 for i in range(a[0])]
		for i in range(a[0]):
			if sl[i] == 1:
				c1 = 0
			else:
				c1 += 1
			if sl[a[0] - i - 1] == 1:
				c2 = 0
			else:
				c2 += 1
			l1[i] = c1
			l2[a[0] - i - 1] = c2
		ans = ''
		for i in range(a[0]):
			if min(l1[i], l2[i]) > 1000000:
				ans += '0'
			elif min(l1[i], l2[i]) > a[1]:
				ans += '0'
			elif min(l1[i], l2[i]) % 2 == a[1] % 2:
				ans += '1'
			else:
				ans += '0'
		print(ans)


import collections
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	prefix_dist = [float('inf')]
	suffix_dist = collections.deque([float('inf')])
	for i in range(1, n):
		if s[i] == s[i - 1]:
			prefix_dist.append(prefix_dist[-1] + 1)
		else:
			prefix_dist.append(1)
		if s[-i - 1] == s[-i]:
			suffix_dist.appendleft(suffix_dist[0] + 1)
		else:
			suffix_dist.appendleft(1)
	res = ''
	for i in range(n):
		dist = min(prefix_dist[i], suffix_dist[i])
		if dist > k:
			res += '0'
		elif (k - dist) % 2 == 0:
			res += str(1 - int(s[i]))
		else:
			res += s[i]
	print(res)


from sys import stdin
input = stdin.readline
inp = lambda : list(map(int, input().split()))

def answer():
	v = a.count('0')
	if v == 0 or v == n:
		return '0' * n
	front = [[-float('inf'), -float('inf')] for i in range(n + 1)]
	for i in range(n):
		front[i + 1] = front[i][:]
		front[i + 1][int(a[i])] = i
	back = [[float('inf'), float('inf')] for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		back[i] = back[i + 1][:]
		back[i][int(a[i])] = i
	ans = ''
	for i in range(n):
		dist = min(i - front[i + 1][int(a[i]) ^ 1], back[i][int(a[i]) ^ 1] - i)
		if dist > k:
			ans += '0'
			continue
		if k - dist & 1 == 0:
			if a[i] == '1':
				ans += '0'
			else:
				ans += '1'
		elif a[i] == '1':
			ans += '1'
		else:
			ans += '0'
	return ans
for T in range(int(input())):
	(n, k) = inp()
	a = input().strip()
	print(answer())


for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	Q = str(input())
	k -= 1
	Q = '.' + Q + '.'
	Q = list(Q)
	b = [x for x in Q]
	a = [0 for i in range(100001)]
	for i in range(1, n + 1):
		if Q[i] == '1':
			b[i] = '0'
			if Q[i - 1] == '0':
				b[i - 1] = '1'
			if Q[i + 1] == '0':
				b[i + 1] = '1'
	Q = b[1:n + 1]
	x = 2147483647
	for i in range(n):
		if Q[i] == '1':
			x = 0
		a[i] = x
		x += 1
	x = 2147483647
	for i in range(n - 1, -1, -1):
		if Q[i] == '1':
			x = 0
		a[i] = min(a[i], x)
		x += 1
	for i in range(n):
		if k < a[i]:
			print('0', end='')
		elif (k - a[i]) % 2 == 0:
			print('1', end='')
		else:
			print('0', end='')
	print()


test = int(input())
for k in range(test):
	(n, s) = map(int, input().split())
	arr = input()
	last_zero = -1
	last_one = -1
	left_toggel = []
	for i in range(n):
		if arr[i] == '0':
			left_toggel.append(last_one)
			last_zero = i
		else:
			left_toggel.append(last_zero)
			last_one = i
	last_zero = -1
	last_one = -1
	right_toggel = [0] * n
	for i in reversed(range(n)):
		if arr[i] == '0':
			right_toggel[i] = last_one
			last_zero = i
		else:
			right_toggel[i] = last_zero
			last_one = i
	result = ''
	for i in range(n):
		left_dist = 10 ** 10
		right_dist = 10 ** 10
		if left_toggel[i] != -1:
			left_dist = i - left_toggel[i]
		if right_toggel[i] != -1:
			right_dist = right_toggel[i] - i
		dist = min(left_dist, right_dist)
		if arr[i] == '0':
			if dist > s:
				result = result + '0'
				continue
			else:
				val = s - dist + 1
				if val % 2 == 0:
					result = result + '0'
				else:
					result = result + '1'
				continue
		elif dist >= s:
			result = result + '0'
			continue
		else:
			val = s - dist + 1
			if val % 2 == 0:
				result = result + '1'
			else:
				result = result + '0'
			continue
	print(result)


for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	(q, k) = (input(), k - 1)
	a = [0 for i in range(100001)]
	q = [x for x in '.' + q + '.']
	b = [x for x in q]
	for j in range(1, n + 1):
		if q[j] == '1':
			b[j] = '0'
			if q[j - 1] == '0':
				b[j - 1] = '1'
			if q[j + 1] == '0':
				b[j + 1] = '1'
	q = b[1:n + 1]
	x = 2147483647
	for i in range(0, n):
		if q[i] == '1':
			x = 0
		a[i] = x
		x += 1
	x = 2147483647
	for i in range(n - 1, -1, -1):
		if q[i] == '1':
			x = 0
		a[i] = min(a[i], x)
		x += 1
	for i in range(n):
		if k < a[i]:
			print('0', end='')
		elif (k - a[i]) % 2 == 0:
			print('1', end='')
		else:
			print('0', end='')
	print()


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input().strip()
	a = [-1] * n
	b = [-1] * n
	ind = -1
	for i in range(n):
		if s[i] == '0':
			ind = i
		elif ind == -1:
			pass
		elif a[i] == -1:
			a[i] = i - ind - 1
		else:
			a[i] = min(a[i], i - ind - 1)
	ind = n
	for i in range(n - 1, -1, -1):
		if s[i] == '0':
			ind = i
		elif ind == n:
			pass
		elif a[i] == -1:
			a[i] = ind - i - 1
		else:
			a[i] = min(a[i], ind - i - 1)
	ind = -1
	for i in range(n):
		if s[i] == '1':
			ind = i
		elif ind == -1:
			pass
		elif a[i] == -1:
			a[i] = i - ind - 1
		else:
			a[i] = min(a[i], i - ind - 1)
	ind = n
	for i in range(n - 1, -1, -1):
		if s[i] == '1':
			ind = i
		elif ind == n:
			pass
		elif a[i] == -1:
			a[i] = ind - i - 1
		else:
			a[i] = min(a[i], ind - i - 1)
	ans = ''
	for i in range(n):
		if s[i] == '0':
			if a[i] < 0:
				ans += '0'
			elif k - a[i] >= 0 and (k - a[i]) % 2 == 1:
				ans += '1'
			else:
				ans += '0'
		else:
			c = 1
			x = k - 1
			if a[i] < 0:
				ans += '0'
			elif x - a[i] >= 0:
				if (c + (x - a[i]) % 2) % 2 == 0:
					ans += '1'
				else:
					ans += '0'
			else:
				ans += '0'
	print(ans)


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	q = input()
	k -= 1
	Q = '.' + q + '.'
	aux = []
	a = [0] * 100001
	for i in range(len(Q)):
		aux.append(Q[i])
	b = aux.copy()
	aux = []
	for i in range(1, n + 1):
		if Q[i] == '1':
			b[i] = '0'
			if Q[i - 1] == '0':
				b[i - 1] = '1'
			if Q[i + 1] == '0':
				b[i + 1] = '1'
	b = ''.join(b)
	for i in range(1, len(b)):
		aux.append(b[i])
	Q = ''.join(aux)
	x = 2147483647
	for i in range(n):
		if Q[i] == '1':
			x = 0
		a[i] = x
		x += 1
	x = 2147483647
	for i in range(n, -1, -1):
		if Q[i] == '1':
			x = 0
		a[i] = min(a[i], x)
		x += 1
	for i in range(n):
		if k < a[i]:
			print('0', end='')
		elif (k - a[i]) % 2 == 0:
			print('1', end='')
		else:
			print('0', end='')
	print(end='\n')
	t -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	r = [float('inf') for i in range(n)]
	l = [float('inf') for i in range(n)]
	le0 = float('-inf')
	le1 = float('-inf')
	for i in range(n):
		if s[i] == '0':
			l[i] = min(i - le1, l[i])
			le0 = i
		else:
			l[i] = min(i - le0, l[i])
			le1 = i
	re0 = float('inf')
	re1 = float('inf')
	for i in range(n - 1, -1, -1):
		if s[i] == '0':
			r[i] = min(re1 - i, l[i])
			re0 = i
		else:
			r[i] = min(re0 - i, l[i])
			re1 = i
	arr = [float('inf') for i in range(n)]
	for i in range(n):
		arr[i] = min(l[i], r[i])
	ans = ''
	for i in range(n):
		if s[i] == '0':
			if arr[i] == float('inf'):
				ans += '0'
			elif k < arr[i]:
				ans += '0'
			else:
				t = k - arr[i] + 1
				if t % 2 == 0:
					ans += '0'
				else:
					ans += '1'
		elif arr[i] == float('inf'):
			ans += '0'
		else:
			t1 = k - 1
			if t1 < arr[i]:
				ans += '0'
			else:
				t = t1 - arr[i] + 1
				if t % 2 == 0:
					ans += '0'
				else:
					ans += '1'
	print(ans)


from collections import deque
from functools import reduce

def thiccness(s):
	last = (float('-inf'), float('-inf'))
	ans = []
	for i in range(len(s)):
		x = s[i]
		last = (i, last[1]) if x == '0' else (last[0], i)
		ans.append(i - last[0] if x == '1' else i - last[1])
	return ans

def solve():
	(n, k) = map(int, input().split())
	s = input()
	a = thiccness(s)
	b = thiccness(s[::-1])[::-1]
	c = [min(x, y) for (x, y) in zip(a, b)]
	ans = ''
	for i in range(n):
		if k < c[i]:
			ans += '0'
		elif (k - c[i]) % 2 == 0:
			ans += str(1 - int(s[i]))
		else:
			ans += s[i]
	return ''.join(ans)
for _ in range(int(input())):
	print(solve())


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	q = input()
	k -= 1
	b = list(q)
	for i in range(n):
		if q[i] != '0':
			b[i] = '0'
			if i != 0 and q[i - 1] != '1':
				b[i - 1] = '1'
			if i != n - 1 and q[i + 1] != '1':
				b[i + 1] = '1'
	a = [99999999999] * n
	m = 2147483647
	for i in range(n):
		if b[i] == '1':
			m = 0
		a[i] = m
		m += 1
	m = 2147483647
	for i in range(n - 1, -1, -1):
		if b[i] == '1':
			m = 0
		a[i] = min(a[i], m)
		m += 1
	for i in range(n):
		if k < a[i]:
			print('0', end='')
		elif (k - a[i]) % 2 == 0:
			print(1, end='')
		else:
			print(0, end='')
	print()


import sys

def prin(a):
	sys.stdout.write(str(a) + '\n')

def input():
	return sys.stdin.readline().strip()

def sol(s):
	ans = list(s)
	n = len(s)
	for i in range(n):
		if s[i] == '1':
			ans[i] = '0'
		elif i > 0 and s[i - 1] == '1' or (i < n - 1 and s[i + 1] == '1'):
			ans[i] = '1'
		else:
			ans[i] == '0'
	return ''.join(ans)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	s = sol(s)
	k -= 1
	if k == 0:
		print(s)
		continue
	x = [sys.maxsize] * n
	if s[0] == '1':
		x[0] = 0
	for i in range(1, n):
		if s[i] == '1':
			x[i] = 0
		else:
			x[i] = x[i - 1] + 1
	y = [sys.maxsize] * n
	if s[-1] == '1':
		y[-1] = 0
	for i in range(n - 2, -1, -1):
		if s[i] == '1':
			y[i] = 0
		else:
			y[i] = y[i + 1] + 1
	ans = []
	for i in range(n):
		ans.append(min(x[i], y[i]))
	w = []
	for i in range(n):
		if ans[i] > k:
			w.append('0')
		else:
			diff = k - ans[i]
			if diff % 2 == 0:
				w.append('1')
			else:
				w.append('0')
	print(''.join(w))


I = lambda : list(map(int, input().split()))
(t,) = I()
for _ in range(t):
	(n, k) = I()
	l = input().strip()
	n = len(l)
	z = l.count('0')
	if z == 0 or z == n:
		print('0' * n)
	else:
		k -= 1
		s = list(l)
		for i in range(n):
			if l[i] == '1':
				s[i] = '0'
			elif i > 0 and l[i - 1] == '1':
				s[i] = '1'
			elif i < n - 1 and l[i + 1] == '1':
				s[i] = '1'
		l = ''.join(s)
		an = ''
		dis = [n + 1] * n
		x = -1
		for i in range(n):
			if l[i] == '1':
				x = i
				dis[i] = 0
			elif x != -1:
				dis[i] = min(i - x, dis[i])
		x = -1
		for i in range(n - 1, -1, -1):
			if l[i] == '1':
				x = i
				dis[i] = 0
			elif x != -1:
				dis[i] = min(x - i, dis[i])
		for i in range(n):
			if l[i] == '1':
				an += str((k - 1) % 2)
			else:
				an += str((k - dis[i] + 1) % 2 if dis[i] <= k else 0)
		print(an)