William really likes the cellular automaton called "Game of Life" so he decided to make his own version. For simplicity, William decided to define his cellular automaton on an array containing $n$ cells, with each cell either being alive or dead.

Evolution of the array in William's cellular automaton occurs iteratively in the following way:

If the element is dead and it has exactly $1$ alive neighbor in the current state of the array, then on the next iteration it will become alive. For an element at index $i$ the neighbors would be elements with indices $i - 1$ and $i + 1$. If there is no element at that index, it is considered to be a dead neighbor.

William is a humane person so all alive elements stay alive.

Check the note section for examples of the evolution.

You are given some initial state of all elements and you need to help William find the state of the array after $m$ iterations of evolution.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^3$). Description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($2 \le n \le 10^3, 1 \le m \le 10^9$), which are the total number of cells in the array and the number of iterations.

The second line of each test case contains a string of length $n$ made up of characters "0" and "1" and defines the initial state of the array. "1" means a cell is alive and "0" means it is dead.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^4$.


-----Output-----

In each test case output a string of length $n$, made up of characters "0" and "1"  — the state of the array after $m$ iterations of evolution.


-----Examples-----

Input
4
11 3
01000000001
10 2
0110100101
5 2
10101
3 100
000
Output
11111001111
1110111101
10101
000


-----Note-----

Sequence of iterations of evolution for the first test case

01000000001  — initial state

11100000011  — first iteration of evolution

11110000111  — second iteration of evolution

11111001111  — third iteration of evolution

Sequence of iterations of evolution for the second test case

0110100101  — initial state

1110111101  — first iteration of evolution

1110111101  — second iteration of evolution

Source: codeforces | Difficulty: EASY
Tags: Implementation


Solutions:
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for t in range(int(input())):
	(n, m) = map(int, input().split())
	s = input()
	l = []
	for i in range(n):
		if s[i] == '1':
			l.append(i)
	ans = list(s)
	if len(l):
		a = l[0] - 1
		while a >= max(0, l[0] - m):
			ans[a] = '1'
			a -= 1
		a = l[-1] + 1
		while a <= min(n - 1, l[-1] + m):
			ans[a] = '1'
			a += 1
		for i in range(len(l) - 1):
			x = l[i + 1] - l[i] - 1
			if x:
				if x % 2:
					a = l[i] + 1
					b = l[i + 1] - 1
					for j in range(min(x // 2, m)):
						ans[a] = '1'
						ans[b] = '1'
						a += 1
						b -= 1
				else:
					a = l[i] + 1
					b = l[i + 1] - 1
					for j in range(min(x // 2, m)):
						ans[a] = '1'
						ans[b] = '1'
						a += 1
						b -= 1
	print(''.join(ans))


t = int(input())
for _ in range(t):
	l = list(map(int, input().split()))
	s = input()
	for i in range(min(l[0], l[-1])):
		while '101' in s:
			s = s.replace('101', '1_1')
		s = s.replace('10', '11')
		s = s.replace('01', '11')
	s = s.replace('_', '0')
	print(s)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	l = input()
	if '1' not in l:
		print(l)
	else:
		pos = []
		l = list(l)
		for i in range(n):
			if l[i] == '1':
				pos.append(i)
		p = pos[0]
		if p != 0:
			for j in range(1, m + 1):
				if p - j >= 0:
					l[p - j] = '1'
				else:
					break
		for i in range(len(pos) - 1):
			p = pos[i]
			p_1 = pos[i + 1]
			d = p_1 - p - 1
			for j in range(1, m + 1):
				if p + j < p_1:
					l[p + j] = '1'
				else:
					break
			for j in range(1, m + 1):
				if p_1 - j > p:
					l[p_1 - j] = '1'
				else:
					break
			if d % 2 == 1:
				l[(p_1 + p) // 2] = '0'
		p = pos[-1]
		if p != n - 1:
			for j in range(1, m + 1):
				if p + j < n:
					l[p + j] = '1'
				else:
					break
		print(''.join(l))


for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	s = input()
	prev = s
	for __ in range(m):
		curr = ''
		for i in range(n):
			if i == 0:
				if s[i] == '0' and s[i + 1] == '1':
					curr += '1'
				else:
					curr += s[i]
			elif i == n - 1:
				if s[i] == '0' and s[i - 1] == '1':
					curr += '1'
				else:
					curr += s[i]
			elif s[i] == '0' and int(s[i - 1]) + int(s[i + 1]) == 1:
				curr += '1'
			else:
				curr += s[i]
		if curr == s:
			break
		s = curr
	print(curr)


import sys
import math
from bisect import bisect_left
import heapq
from collections import deque

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

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

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

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

def C(n, k, mod):
	return FACT(n, mod) * pow(FACT(k, mod) * FACT(n - k, mod) % mod, mod - 2, mod) % mod

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)
mod = 10 ** 9 + 7
for _ in range(II()):
	(n, m) = MI()
	s = list(SI())
	if m == 0:
		print(''.join(s))
	else:
		newS = s[:]
		while True:
			m -= 1
			inds = []
			for i in range(n):
				if s[i] == '0':
					if i == 0:
						if s[i + 1] == '1':
							newS[i] = '1'
					elif i == n - 1:
						if s[i - 1] == '1':
							newS[i] = '1'
					elif s[i - 1] != s[i + 1]:
						newS[i] = '1'
			if s == newS or m == 0:
				break
			s = newS[:]
	print(''.join(newS))


q = int(input())
for z in range(q):
	(n, m) = map(int, input().split())
	l = input()
	ar = []
	for i in range(n):
		ar = ar + [int(l[i])]
	i = 0
	while i < n and ar[i] == 0:
		i += 1
	j = i + 1
	if i >= n:
		ar1 = ar
	elif i > m - 1:
		ar1 = [0] * (i - m) + [1] * (m + 1)
	else:
		ar1 = [1] * (i + 1)
	while True:
		while j < n and ar[j] == 0:
			j += 1
		if j < n:
			if j - i - 1 >= 2 * m:
				ar1 += [1] * m + [0] * (j - i - 2 * m - 1) + [1] * (m + 1)
			else:
				k = j - i - 1
				ar1 += [1] * (k // 2)
				if k % 2 == 1:
					ar1 += [0]
				ar1 += [1] * (k // 2 + 1)
		else:
			break
		i = j
		j += 1
	if i >= n:
		pass
	elif n - i - 1 >= m:
		ar1 += [1] * m + [0] * (n - i - m - 1)
	else:
		ar1 += [1] * (n - i - 1)
	for i in range(n):
		print(ar1[i], end='')
	print('')


retList = []
for i in range(int(input())):
	(n, m) = list(map(int, input().split()))
	Data = input().split('1')
	if len(Data) == 1:
		retList.append(Data[0])
		continue
	retStr = ''
	if len(Data[0]) < m:
		retStr = '1' * len(Data[0]) + '1'
	else:
		retStr = '0' * (len(Data[0]) - m) + '1' * (m + 1)
	for j in range(1, len(Data) - 1):
		if len(Data[j]) <= 2 * m:
			if len(Data[j]) % 2 == 0:
				retStr += '1' * len(Data[j]) + '1'
			else:
				retStr += '1' * (len(Data[j]) // 2) + '0' + '1' * (len(Data[j]) // 2) + '1'
		else:
			retStr += '1' * m + '0' * (len(Data[j]) - 2 * m) + '1' * (m + 1)
	if len(Data[-1]) < m:
		retStr += '1' * len(Data[-1])
	else:
		retStr += '1' * m + '0' * (len(Data[-1]) - m)
	retList.append(retStr)
print('\n'.join(retList))


from itertools import groupby
cases = int(input())
for _ in range(cases):
	(n, k) = map(int, input().split())
	s = input()
	ones = s.count('1')
	if ones == 0:
		print(s)
	else:
		first_one = True
		last_one = False
		ans = []
		for (i, grp) in groupby(s):
			lst = list(grp)
			ln = len(lst)
			if i == '1':
				ones -= ln
				ans.extend(lst)
				if ones == 0:
					last_one = True
				first_one = False
			if i == '0' and first_one:
				if k >= ln:
					ans.extend(['1'] * ln)
				else:
					ans.extend(['0'] * (ln - k) + ['1'] * k)
				first_one = False
			elif i == '0' and last_one:
				if k >= ln:
					ans.extend(['1'] * ln)
				else:
					ans.extend(['1'] * k + ['0'] * (ln - k))
			elif i == '0':
				if ln % 2 == 0:
					if k >= ln // 2:
						ans.extend(['1'] * ln)
					else:
						ans.extend(['1'] * k + ['0'] * (ln // 2 - k) + ['0'] * (ln // 2 - k) + ['1'] * k)
				else:
					md = ln // 2
					ans.extend(['1'] * min(k, md) + ['0'] * (ln - 2 * min(k, md)) + ['1'] * min(k, md))
		print(''.join(ans))


def first(x, m):
	l = len(x)
	if l > m:
		return '0' * (l - m) + '1' * m
	else:
		return '1' * l

def last(x, m):
	l = len(x)
	if l > m:
		return '1' * m + '0' * (l - m)
	else:
		return '1' * l

def middle(x, m):
	l = len(x)
	if l > 2 * m:
		return '1' * m + '0' * (l - 2 * m) + '1' * m
	elif l % 2 == 0:
		return '1' * l
	else:
		return '1' * (l // 2) + '0' + '1' * (l // 2)
t = int(input())
for i in range(t):
	inp = input().split()
	(n, m, inp) = (int(inp[0]), int(inp[1]), input())
	inp = inp.split('1')
	if len(inp) != 1:
		inp[0] = first(inp[0], m)
		inp[-1] = last(inp[-1], m)
		for j in range(1, len(inp) - 1):
			inp[j] = middle(inp[j], m)
		print('1'.join(inp))
	else:
		print(inp[0])


for t in range(int(input())):
	(n, m) = map(int, input().split())
	s = input()
	s = '0' + s + '0'
	for i in range(min(m, n)):
		while '101' in s:
			s = s.replace('101', '121')
		s = s.replace('10', '11')
		s = s.replace('01', '11')
	while '121' in s:
		s = s.replace('121', '101')
	print(s[1:n + 1])


from sys import stdin, stdout
from math import ceil, floor, sqrt, log, log2, log10
from collections import Counter
int_max = float('inf')
int_min = -float('inf')
input = stdin.readline

def solve():
	pass
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	arr = list(input())
	arr.pop(-1)
	arr = list(map(int, arr))
	output = arr[:]
	z = arr.count(0)
	previousZ = z
	k = 0
	while k < m:
		for i in range(n):
			if i == 0:
				if arr[i] == 0 and arr[i + 1] == 1:
					output[i] = 1
					z -= 1
			elif i == n - 1:
				if arr[i] == 0 and arr[i - 1] == 1:
					output[i] = 1
					z -= 1
			elif arr[i] == 0 and arr[i - 1] ^ arr[i + 1] == 1:
				output[i] = 1
				z -= 1
		if previousZ == z:
			break
		else:
			arr = output[:]
			previousZ = z
		k += 1
	print(*output, sep='')


from collections import defaultdict
tc = int(input())
for _ in range(tc):
	(n, m) = list(map(int, input().split()))
	s = input()
	a = list(s)
	oi = []
	for i in range(n):
		if a[i] == '1':
			oi.append(i)
	if len(oi) == 0:
		print(s)
		continue
	if len(oi) == 1:
		c = 0
		for i in range(oi[0] + 1, n):
			a[i] = '1'
			c += 1
			if c == m:
				break
		c = 0
		for i in range(oi[0] - 1, -1, -1):
			a[i] = '1'
			c += 1
			if c == m:
				break
		print(''.join(a))
		continue
	if a[0] == '0' and a[1] == '1':
		a[0] = '1'
	c = 0
	for i in range(oi[-1] + 1, n):
		a[i] = '1'
		c += 1
		if c == m:
			break
	c = 0
	for i in range(oi[0] - 1, -1, -1):
		a[i] = '1'
		c += 1
		if c == m:
			break
	for i in range(1, len(oi)):
		d = (oi[i] - oi[i - 1] - 1) // 2
		c = 0
		for j in range(oi[i - 1] + 1, oi[i]):
			if c == min(m, d):
				break
			c += 1
			a[j] = '1'
		c = 0
		for j in range(oi[i] - 1, oi[i - 1], -1):
			if c == min(m, d):
				break
			c += 1
			a[j] = '1'
	print(''.join(a))


for t in range(int(input())):
	(n, m) = map(int, input().split())
	a = [int(x) for x in input()]
	left = []
	right = []
	k = -1
	for i in range(n):
		if a[i] == 1:
			k = i
		left.append(n + 1 if k == -1 else i - k)
	k = -1
	for i in range(n - 1, -1, -1):
		if a[i] == 1:
			k = i
		right.insert(0, n + 1 if k == -1 else k - i)
	for i in range(n):
		if left[i] != 0 and left[i] == right[i]:
			a[i] = 0
		else:
			a[i] = 1 if min(left[i], right[i]) <= m else 0
	print(''.join([str(x) for x in a]))


import sys
from os import path
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
import math
t = int(input())
while t:
	t -= 1
	(n, m) = map(int, input().split())
	s = input()
	s = [i for i in s]
	if '1' not in s:
		print(''.join(s))
		continue
	else:
		new = []
		while m >= 0:
			m -= 1
			if new == s:
				break
			new = s.copy()
			if s[1] == '1':
				s[0] = '1'
			if s[-2] == '1':
				s[-1] = '1'
			for i in range(1, n - 1):
				if new[i + 1] != new[i - 1] or new[i + 1] == new[i - 1] == 0:
					s[i] = '1'
		sd = ''.join(new)
		print(sd)


t = int(input())
for j in range(t):
	(n, m) = map(int, input().split())
	a = input()
	x = []
	d = len(a)
	a = int(a)
	for i in range(d):
		x.append(a % 10)
		a = a // 10
	x = x[::-1]
	l = x
	arr = l[:]
	for i in range(min(m, n)):
		for k in range(n):
			if x[k] == 0:
				if k >= 1 and k < n - 1:
					if x[k - 1] ^ x[k + 1] == 1:
						arr[k] = 1
				elif k == 0:
					if x[k + 1] == 1:
						arr[k] = 1
				elif x[k - 1] == 1:
					arr[k] = 1
		x = arr[:]
	print(*arr, sep='')


tcs = int(input())
for tc in range(tcs):
	(n, m) = list(map(int, input().split()))
	s = input()
	for i in range(min(n, m)):
		while '101' in s:
			s = s.replace('101', '121')
		s = s.replace('10', '11')
		s = s.replace('01', '11')
	while '121' in s:
		s = s.replace('121', '101')
	print(s)


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	s = list(map(int, input()))
	for j in range(1, a):
		if s[j] == 1:
			continue
		if s[j - 1] != 0 and s[j] == 0 and (s[j - 1] + 1 <= b + 1):
			s[j] = s[j - 1] + 1
	for j in reversed(range(1, a)):
		if (s[j - 1] > s[j] + 1 or s[j - 1] == 0) and s[j] != 0 and (s[j] + 1 <= b + 1):
			s[j - 1] = s[j] + 1
		elif s[j - 1] == s[j] + 1 and s[j] != 0:
			s[j - 1] = 0
	ans = ''
	for i in s:
		if i == 0:
			ans += '0'
		else:
			ans += '1'
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = list(input())
	ones = []
	x = 0
	while x < min(n, m):
		s1 = s.copy()
		for i in range(1, n - 1):
			if s[i] == '0':
				y = 0
				if s[i - 1] == '1':
					y += 1
				if s[i + 1] == '1':
					y += 1
				if y == 1:
					s1[i] = '1'
		if s[0] == '0' and n >= 2 and (s[1] == '1'):
			s1[0] = '1'
		if s[-1] == '0' and n >= 2 and (s[-2] == '1'):
			s1[-1] = '1'
		s = s1.copy()
		x += 1
	ans = ''.join(s)
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = input()
	l = []
	for i in range(len(s)):
		if s[i] == '1':
			l.append(i)
	if not l:
		print(s)
	else:
		r = ''
		if l[0] <= m:
			r += '1' * (l[0] + 1)
		else:
			r += '0' * (l[0] - m) + '1' * (m + 1)
		for i in range(1, len(l)):
			k = l[i] - l[i - 1]
			if k <= 2 * m:
				if k % 2 == 0:
					r += '1' * (k // 2 - 1) + '0' + '1' * (k // 2)
				else:
					r += '1' * (k // 2) + '1' * (k // 2 + 1)
			else:
				r += '1' * m + '0' * (k - 2 * m - 1) + '1' * (m + 1)
		if l[-1] < n - 1:
			if n - 1 - l[-1] <= m:
				r += '1' * (n - 1 - l[-1])
			else:
				r += '1' * m + '0' * (n - 1 - l[-1] - m)
		print(r)


for _ in range(int(input())):
	(n, m) = list(map(int, input().strip().split()))
	s = input()
	ans = [i for i in s]
	ref = []
	for i in range(n):
		if s[i] == '1':
			ref.append(i)
	for i in range(len(ref) - 1):
		j = i + 1
		m1 = m
		l = ref[i] + 1
		r = ref[j] - 1
		while l < r and m1 > 0:
			ans[l] = '1'
			ans[r] = '1'
			l += 1
			r -= 1
			m1 -= 1
	if len(ref) > 0:
		l = ref[0] - 1
		m1 = m
		while l > -1 and m1 > 0:
			ans[l] = '1'
			l -= 1
			m1 -= 1
		r = ref[-1] + 1
		m1 = m
		while r < n and m1 > 0:
			ans[r] = '1'
			r += 1
			m1 -= 1
	for i in ans:
		print(i, end='')
	print('')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ar = list(map(int, list(input())))
	p1 = 0
	while p1 < n:
		while p1 < n and ar[p1] != 0:
			p1 += 1
		p2 = p1
		while p2 < n - 1 and ar[p2 + 1] != 1:
			p2 += 1
		if p1 == 0 and p2 == n - 1:
			break
		elif p1 == 0:
			np2 = p2
			i = m
			while i > 0 and np2 >= 0:
				ar[np2] = 1
				np2 -= 1
				i -= 1
		elif p2 == n - 1:
			np1 = p1
			i = m
			while i > 0 and np1 < n:
				ar[np1] = 1
				np1 += 1
				i -= 1
		else:
			np1 = p1
			np2 = p2
			i = m
			while i > 0 and np1 < np2:
				ar[np1] = 1
				ar[np2] = 1
				np1 += 1
				np2 -= 1
				i -= 1
		p1 = p2 + 1
	for i in ar:
		print(i, end='')
	print()


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect, insort
from time import perf_counter
from fractions import Fraction
import copy
from copy import deepcopy
import time
starttime = time.time()
mod = int(pow(10, 9) + 7)
mod2 = 998244353

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

def out(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def L():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
try:
	sys.stdin = open('input.txt', 'r')
except:
	pass

def pmat(A):
	for ele in A:
		print(*ele, end='\n')
for _ in range(L()[0]):
	(n, m) = L()
	A = ['0'] + list(input()) + ['0']
	cnt = 0
	while cnt < m:
		B = [A[i] for i in range(n + 2)]
		for i in range(1, n + 1):
			if A[i] == '0' and A[i - 1] != A[i + 1]:
				B[i] = '1'
		if B == A:
			break
		A = B[:]
		cnt += 1
	print(''.join(B[1:n + 1]))
endtime = time.time()


import math
test = 1
test = int(input())
for tc in range(test):
	l = list(map(int, input().split()))
	if l[1] > l[0]:
		l[1] = l[0]
	s = input()
	for i in range(l[1]):
		while '101' in s:
			s = s.replace('101', '121')
		s = s.replace('01', '11')
		s = s.replace('10', '11')
	s = s.replace('2', '0')
	print(s)


def get_input():
	return next([]) if fake else input()

def get_neighbour(i):
	return ar[i] if 0 <= i < n else 0

def n_neighbours(i):
	return get_neighbour(i - 1) + get_neighbour(i + 1)

def life_iter(ar):
	just_mod = 0
	changes_made = False
	for (i, el) in enumerate(ar):
		if el == 0 and n_neighbours(i) - just_mod == 1:
			ar[i] = 1
			just_mod = 1
			changes_made = True
		else:
			just_mod = 0
	return (ar, changes_made)
fake = False
t = int(get_input())
for i in range(t):
	(n, m) = map(int, get_input().split())
	s_in = get_input()
	ar = [int(c) for c in s_in]
	for k in range(m):
		(ar, changes_made) = life_iter(ar)
		if not changes_made:
			break
	print(''.join(map(str, ar)))


def solve():
	(N, M) = list(map(int, input().split()))
	S = input()
	d1 = [int(10000000000.0) for _ in range(N)]
	d2 = [int(10000000000.0) for _ in range(N)]
	ans = ['0' for _ in range(N)]
	last = -int(10000000000.0)
	for i in range(0, N):
		if S[i] == '1':
			last = i
		d1[i] = i - last
	last = int(10000000000.0)
	for i in range(N - 1, -1, -1):
		if S[i] == '1':
			last = i
		d2[i] = last - i
	for i in range(0, N):
		if S[i] == '1':
			ans[i] = '1'
		elif d1[i] == d2[i]:
			ans[i] = '0'
		elif d1[i] <= M or d2[i] <= M:
			ans[i] = '1'
		else:
			ans[i] = '0'
	print(''.join(ans))
T = int(input())
for _ in range(T):
	solve()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = input()
	if a.count('1') == 0:
		print(a)
		continue
	cnt = 0
	b = []
	for i in range(n):
		if a[i] == '0':
			cnt += 1
		else:
			b.append(cnt)
			cnt = 0
	b.append(cnt)
	n1 = len(b)
	ans = ''
	if b[0] <= m:
		ans += '1' * b[0]
	else:
		ans += '0' * (b[0] - m)
		ans += '1' * m
	ans += '1'
	for i in range(1, n1 - 1):
		if b[i] == 0:
			ans += '1'
		else:
			if b[i] <= 2 * m:
				if b[i] % 2 == 0:
					ans += '1' * b[i]
				else:
					ans += '1' * (b[i] // 2)
					ans += '0'
					ans += '1' * (b[i] // 2)
			else:
				ans += '1' * m
				ans += '0' * (b[i] - m - m)
				ans += '1' * m
			ans += '1'
	if b[-1] <= m:
		ans += '1' * b[-1]
	else:
		ans += '1' * m
		ans += '0' * (b[-1] - m)
	print(ans)


def life(n, m, s):
	a = s.copy()
	for _ in range(min(n, m)):
		for i in range(n):
			if s[i] == 0:
				if i == 0:
					if s[1] == 1:
						a[i] = 1
				elif i == n - 1:
					if s[n - 2] == 1:
						a[i] = 1
				elif s[i - 1] + s[i + 1] == 1:
					a[i] = 1
		s = a.copy()
	print(*s, sep='')
z = int(input())
for i in range(0, z):
	(q, w) = map(int, input().split())
	l = [int(i) for i in list(input())]
	life(q, w, l)


def solN():
	(n, m) = map(int, input().split())
	r = list(input())
	(l, c) = ([], 0)
	for i in range(n):
		if r[i] == '0':
			l.append(i)
			c += 1
	if c == n:
		for i in r:
			print(i, end='')
		print()
		return
	if m > n:
		for _ in range(n):
			(k, j, i, a) = ([], 1, 0, c)
			while j <= c:
				if l[i] == 0:
					if r[1] == '1':
						k.append(l[i])
						l.pop(i)
						a -= 1
					else:
						i += 1
				elif l[i] == n - 1:
					if r[n - 2] == '1':
						k.append(l[i])
						l.pop(i)
						a -= 1
				elif r[l[i] - 1] != '1' and r[l[i] + 1] == '1':
					k.append(l[i])
					l.pop(i)
					a -= 1
				elif r[l[i] - 1] == '1' and r[l[i] + 1] != '1':
					k.append(l[i])
					l.pop(i)
					a -= 1
				else:
					i += 1
				j += 1
			for j in k:
				r[j] = '1'
			if l == []:
				break
			c = a
		for i in r:
			print(i, end='')
		print()
	else:
		for _ in range(m):
			(k, j, i, a) = ([], 1, 0, c)
			while j <= c:
				if l[i] == 0:
					if r[1] == '1':
						k.append(l[i])
						l.pop(i)
						a -= 1
					else:
						i += 1
				elif l[i] == n - 1:
					if r[n - 2] == '1':
						k.append(l[i])
						l.pop(i)
						a -= 1
				elif r[l[i] - 1] != '1' and r[l[i] + 1] == '1':
					k.append(l[i])
					l.pop(i)
					a -= 1
				elif r[l[i] - 1] == '1' and r[l[i] + 1] != '1':
					k.append(l[i])
					l.pop(i)
					a -= 1
				else:
					i += 1
				j += 1
			for j in k:
				r[j] = '1'
			if l == []:
				break
			c = a
		for i in r:
			print(i, end='')
		print()

def main():
	for _ in range(int(input())):
		solN()
main()


def solve(li):
	x = 0
	copyofli = li[:]
	while x < len(li):
		if x == 0:
			if li[x] == 0 and li[x + 1] == 1:
				copyofli[x] = 1
		elif x == len(li) - 1:
			if li[x] == 0 and li[x - 1] == 1:
				copyofli[x] = 1
		elif li[x] == 0:
			if li[x - 1] == 1 and li[x + 1] == 0 or (li[x - 1] == 0 and li[x + 1] == 1):
				copyofli[x] = 1
		x += 1
	return copyofli
tc = int(input())
for _ in range(tc):
	(size, iterations) = map(int, input().split())
	st = input()
	s = [int(x) for x in st]
	if s[0] == 0 and len(set(s)) == 1:
		print(st)
	else:
		while iterations != 0:
			prev = s
			ans = solve(s)
			if prev == ans:
				break
			s = ans
			iterations -= 1
		print(*ans, sep='')


from collections import defaultdict, deque
from random import randint

def solve(n, m, s):
	result = [int(s[i]) for i in range(n)]
	for j in range(m):
		changed = False
		xPrev = 0
		for i in range(n):
			if i < n - 1:
				xNext = result[i + 1]
			else:
				xNext = 0
			xCurr = result[i]
			if xPrev + xNext == 1 and result[i] == 0:
				result[i] = 1
				changed = True
			xPrev = xCurr
		if not changed:
			break
	return ''.join([str(x) for x in result])
t = int(input())
results = []
for _ in range(t):
	(n, m) = map(int, input().split(' '))
	s = input()
	result = solve(n, m, s)
	results.append(result)
for result in results:
	print(result)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = input().strip()
	segs = []
	for i in range(n):
		if s[i] == '1':
			if i and s[i - 1] == 1:
				segs[-1][1] += 1
			else:
				segs.append([i, i])
	for i in range(len(segs)):
		if i == 0:
			segs[i][0] -= m
			segs[i][0] = max(segs[i][0], 0)
		if i == len(segs) - 1:
			segs[i][1] += m
			segs[i][1] = min(segs[i][1], n - 1)
		if i < len(segs) - 1:
			dist = segs[i + 1][0] - segs[i][1] - 1
			if dist >= 2 * m:
				segs[i + 1][0] -= m
				segs[i][1] += m
			else:
				segs[i + 1][0] -= dist // 2
				segs[i][1] += dist // 2
	out = ['0' for i in range(n)]
	for seg in segs:
		for i in range(seg[0], seg[1] + 1):
			out[i] = '1'
	print(''.join(out))


import sys
MOD = 1000000007

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

def ii():
	return int(inp())

def iis():
	return [int(i) for i in inp().split()]

def solve():
	(n, m) = iis()
	m = min(n, m)
	a = inp()
	for _ in range(m):
		while '101' in a:
			a = a.replace('101', '121')
		a = a.replace('10', '11')
		a = a.replace('01', '11')
	a = a.replace('2', '0')
	return a
t = ii()
for _ in range(t):
	print(solve())


for t in range(int(input())):
	(n, m) = list(map(int, input().split(' ')))
	arr = list(map(int, [c for c in input()]))
	arr_ = arr[:]
	for _ in range(min(m, n)):
		if arr[1] == 1:
			arr_[0] = 1
		if arr[-2] == 1:
			arr_[-1] = 1
		for i in range(1, n - 1):
			arr_[i] |= (arr[i - 1] == 1) ^ (arr[i + 1] == 1)
		arr = arr_[:]
	print(*arr, sep='')


for _ in range(int(input())):
	s = [int(i) for i in input().split()][1]
	x = input()
	a = -1
	ans = []
	ans_str = ''
	try:
		if '1' in x:
			for i in range(len(x)):
				if x[i] == '0' and a == -1:
					a = i
				elif a != -1 and x[i] == '1':
					if a != i - 1 or a == 0:
						ans.append([a, i - 1])
					a = -1
				if i == len(x) - 1 and x[i] == '0':
					ans.append([a, i])
		if ans:
			a = 0
			for i in ans:
				q = i[1] + 1 - i[0]
				if i[0] == 0:
					ans_str += '1' * q if q <= s else '0' * (q - s) + '1' * s
					a = i[1] + 1
				elif i[1] == len(x) - 1:
					ans_str += x[a:i[0]]
					ans_str += '1' * q if q <= s else '1' * s + '0' * (q - s)
					a = i[1] + 1
				else:
					ans_str += x[a:i[0]]
					if q % 2 == 0:
						ans_str += '1' * q if q / 2 <= s else '1' * s + '0' * (q - 2 * s) + '1' * s
					else:
						ans_str += '1' * ((q - 1) // 2) + '0' + '1' * ((q - 1) // 2) if q / 2 <= s else '1' * s + '0' * (q - 2 * s) + '1' * s
					a = i[1] + 1
			if a != len(x):
				ans_str += x[a:]
	except:
		ans_str = ''
	print(ans_str if ans_str else x)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = input()
	new = []
	for i in s:
		new.append(i)
	k = 0
	while k < m:
		count = 0
		temp = new[:]
		if n >= 2 and new[1] == '1' and (new[0] == '0'):
			temp[0] = '1'
			count += 1
		if n >= 2 and new[-2] == '1' and (new[-1] == '0'):
			temp[-1] = '1'
			count += 1
		for i in range(1, n - 1):
			if new[i] == '0' and (new[i - 1] == '1' and new[i + 1] != '1' or (new[i - 1] != '1' and new[i + 1] == '1')):
				temp[i] = '1'
				count += 1
		new = temp[:]
		k += 1
		if count == 0:
			break
	print(''.join(new))


import sys, os
import math
if os.path.exists('in.txt'):
	sys.stdin = open('in.txt', 'r')
from io import BytesIO, IOBase

def ans(a, m):
	if m == 0:
		return a
	a = list(a)
	if len(set(a)) == 1:
		return a
	if len(a) == 1:
		return a
	if len(a) == 2:
		if a[0] == '0' and a[1] == '1' and (m > 0):
			return ['1', '1']
		elif a[0] == '1' and a[1] == '0' and (m > 0):
			return ['1', '1']
		else:
			return a
	x = []
	for i in range(len(a)):
		j = i - 1
		k = i + 1
		if a[i] == '1':
			x.append(a[i])
		else:
			if j < 0:
				if a[k] == '1':
					x.append('1')
				else:
					x.append('0')
			if k == len(a):
				if a[j] == '1':
					x.append('1')
				else:
					x.append('0')
			if j >= 0 and k < len(a):
				if a[j] == '1' and a[k] == '0':
					x.append('1')
				elif a[j] == '0' and a[k] == '1':
					x.append('1')
				else:
					x.append('0')
	x_new = a
	m -= 1
	while m != 0 and x != x_new:
		x_new = x
		a = x
		x = []
		m -= 1
		for i in range(len(a)):
			j = i - 1
			k = i + 1
			if a[i] == '1':
				x.append(a[i])
			else:
				if j < 0:
					if a[k] == '1':
						x.append('1')
					else:
						x.append('0')
				if k == len(a):
					if a[j] == '1':
						x.append('1')
					else:
						x.append('0')
				if j >= 0 and k < len(a):
					if a[j] == '1' and a[k] == '0':
						x.append('1')
					elif a[j] == '0' and a[k] == '1':
						x.append('1')
					else:
						x.append('0')
	return x

def main():
	for _ in range(int(input())):
		(n, m) = MI()
		a = input()
		fin = ans(a, m)
		fin = ''.join(fin)
		print(fin)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

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

def outP(var):
	sys.stdout.write(str(var) + '\n')
MOD = 10 ** 9 + 7
mod = 998244353
main()


def sol(A, n):
	ones = []
	for i in range(len(A)):
		if A[i] == '1':
			ones.append(i)
	ans = ''
	if len(ones) == 0:
		return A
	l = ones[0]
	ans += '0' * (l - min(n, l)) + '1' * min(n, l)
	ans += '1'
	for i in range(len(ones) - 1):
		l = ones[i + 1] - ones[i] - 1
		if l > 0:
			ans += '1' * min(n, l // 2) + '0' * (l - 2 * min(n, l // 2)) + '1' * min(n, l // 2)
		ans += '1'
	l = len(A) - ones[-1] - 1
	ans += '1' * min(n, l) + '0' * (l - min(n, l))
	return ans
x = int(input())
for _ in range(x):
	y = list(map(int, input().split()))
	A = input()
	print(sol(A, y[1]))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = [0] + list(map(int, input())) + [0]
	temp = [0] * (n + 2)
	for i in range(m):
		if s == temp:
			break
		temp = s.copy()
		temp1 = s.copy()
		for i in range(1, n + 1):
			if s[i] == 0:
				if s[i - 1] + s[i + 1] == 1:
					temp1[i] = 1
		s = temp1.copy()
	ans = ''
	for i in s[1:-1]:
		ans += str(i)
	print(ans)


from itertools import *
I = input
for _ in [0] * int(I()):
	m = int(I().split()[1])
	for i in range((n := len((a := [[k, len([*g])] for (k, g) in groupby(I())])))):
		if a[i][0] < '1':
			d = min(m, a[i][1] >> (0 < i < n - 1))
			if i:
				a[i][1] -= d
				a[i - 1][1] += d
			if i < n - 1:
				a[i][1] -= d
				a[i + 1][1] += d
	print(''.join((k * l for (k, l) in a)))


import sys
lines = [line.rstrip() for line in sys.stdin]
for l in range(1, len(lines), 2):
	nIter = int(lines[l].split()[1])
	arr = [int(i) for i in list(lines[l + 1])]
	indices = []
	for i in range(len(arr)):
		if arr[i] == 1:
			indices.append(i)
	for i in range(len(indices) - 1):
		mid = (indices[i] + indices[i + 1]) / 2
		if mid == int(mid):
			mid = int(mid)
			arr[mid] = -1
	for i in range(len(indices)):
		lo = indices[i] - nIter
		if i > 0:
			lo = max(lo, indices[i - 1])
		lo = max(lo, 0)
		hi = indices[i] + nIter
		if i < len(indices) - 1:
			hi = min(hi, indices[i + 1])
		hi = min(hi, len(arr) - 1)
		for j in range(lo, hi + 1):
			if arr[j] != -1:
				arr[j] = 1
	arr = [str(max(i, 0)) for i in arr]
	print(''.join(arr))


from bisect import bisect
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	s = input()
	arr = list(s)
	ones = [i for i in range(n) if arr[i] == '1']
	n1 = len(ones)
	if n1 == 0:
		print(s)
		continue
	for i in range(n):
		if arr[i] == '1':
			continue
		pos = bisect(ones, i)
		if pos == n1:
			if i - ones[pos - 1] <= m:
				arr[i] = '1'
		elif pos == 0:
			if ones[pos] - i <= m:
				arr[i] = '1'
		elif ones[pos] - i == i - ones[pos - 1]:
			continue
		elif min(ones[pos] - i, i - ones[pos - 1]) <= m:
			arr[i] = '1'
	print(''.join(arr))


import math
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	s = input()
	a = [m + 1] * n
	cur_dis = 0
	for i in range(n):
		if s[i] == '1':
			a[i] = 0
			cur_dis = 1
		elif s[i] == '0' and cur_dis != 0:
			a[i] = cur_dis
			cur_dis += 1
	cur_dis = 0
	for i in range(n - 1, -1, -1):
		if s[i] == '1':
			a[i] = 0
			cur_dis = 1
		elif s[i] == '0' and cur_dis != 0:
			if a[i] == cur_dis:
				a[i] = m + 1
			else:
				a[i] = min(a[i], cur_dis)
			cur_dis += 1
	ans = ''
	for i in range(n):
		if a[i] <= m:
			ans += '1'
		else:
			ans += '0'
	print(ans)


def solution(n, m, array):
	pos = []
	for i in range(n):
		if array[i] == 1:
			pos.append(i)
	if len(pos) == 0:
		return ''.join(map(str, array))
	idx = pos[0]
	while idx >= 0 and pos[0] - idx <= m:
		array[idx] = 1
		idx -= 1
	idx = pos[-1]
	while idx < n and idx - pos[-1] <= m:
		array[idx] = 1
		idx += 1
	for i in range(0, len(pos) - 1):
		idx = pos[i]
		while idx < n and idx - pos[i] <= m and (idx < pos[i + 1]):
			array[idx] = 1
			idx += 1
	for i in range(1, len(pos)):
		idx = pos[i]
		while idx >= 0 and pos[i] - idx <= m and (idx > pos[i - 1]):
			array[idx] = 1
			idx -= 1
	for i in range(1, len(pos)):
		if (pos[i] - pos[i - 1]) % 2 == 0:
			array[(pos[i] + pos[i - 1]) // 2] = 0
	return ''.join(map(str, array))
t = int(input())
for tt in range(t):
	(n, m) = map(int, input().split())
	array = list(map(int, list(input())))
	print(solution(n, m, array))


def check_neighbors(index):
	if index == 0:
		if ans[index + 1] == '1':
			lst[index] = True
			return True
		return False
	if index == n - 1:
		if ans[index - 1] == '1':
			lst[index] = True
			return True
		return False
	if ans[index - 1] == ans[index + 1] == '1':
		lst[index] = True
		return False
	if ans[index - 1] != ans[index + 1]:
		lst[index] = True
		return True
for _ in range(int(input())):
	(n, its) = map(int, input().split())
	lst = [False for i in range(n)]
	ans = list(str(input()))
	count = 0
	for it in range(its):
		change = []
		if count == n:
			break
		for num in range(n):
			if not lst[num] and ans[num] == '1':
				lst[num] = True
				count += 1
			elif not lst[num] and check_neighbors(num):
				change.append(num)
				count += 1
		for ind in change:
			ans[ind] = '1'
		if len(change) == 0:
			break
	ret = ''
	for i in ans:
		ret += i
	print(ret)


t = int(input())
INF = 1000500700
for _ in range(t):
	(n, m) = map(int, input().split())
	s = input()
	r = [INF] * n
	f = False
	d = 0
	for i in range(n):
		if s[i] == '1':
			f = True
			d = 0
			r[i] = 0
			k = i - 1
			while k >= 0 and i - k < r[k]:
				r[k] = i - k
				k -= 1
			if k > 0 and i - k == r[k]:
				r[k] = INF
		elif f:
			d += 1
			r[i] = d
	for i in range(n):
		print('1' if m >= r[i] else '0', end='')
	print()


answers = []

def solve(n, m, s):
	store = []
	for (i, ele) in enumerate(s):
		if ele == '1':
			store.append(i)
	length = len(store)
	if length == 0:
		answers.append(s)
		return
	final = []
	for i in range(length - 1):
		if store[i + 1] - store[i] > 2:
			final.append([store[i] + 1, store[i + 1] - 1])
	first = min(m, store[0])
	last = min(m, n - store[-1])
	finalArray = list(s)
	start = store[0] - 1
	end = store[0] - first
	i = start
	while i >= end and i >= 0:
		finalArray[i] = '1'
		i -= 1
	start = store[-1] + 1
	end = store[-1] + last
	i = start
	while i <= end and i < n:
		finalArray[i] = '1'
		i += 1
	for ele in final:
		start = ele[0]
		end = ele[1]
		length = end - start + 1
		count = 0
		while start < end and count < m:
			finalArray[start] = '1'
			finalArray[end] = '1'
			count += 1
			start += 1
			end -= 1
	ans = ''
	for ele in finalArray:
		ans += ele
	answers.append(ans)
T = int(input())
while T:
	(n, m) = [int(x) for x in input().split()]
	s = input()
	solve(n, m, s)
	T -= 1
for ans in answers:
	print(ans)


import sys
from collections import deque, defaultdict as dd
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input()

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

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def solve():
	for _ in range(ii()):
		(n, m) = li()
		s = si()
		ones = []
		for i in range(n):
			if s[i] == '1':
				ones.append(i)
		out = ''
		if len(ones) == 0:
			print(s)
		else:
			for i in range(len(ones)):
				if i == 0:
					if ones[i] >= m:
						out += (ones[i] - m) * '0' + (m + 1) * '1'
					else:
						out += (ones[i] + 1) * '1'
				if i == len(ones) - 1:
					if n - ones[i] - 1 >= m:
						out += m * '1' + (n - ones[i] - m - 1) * '0'
					else:
						out += (n - ones[i] - 1) * '1'
				elif (ones[i + 1] - ones[i]) % 2 != 0:
					if m <= (ones[i + 1] - ones[i]) // 2:
						out += m * '1' + ((ones[i + 1] - ones[i]) // 2 - m) * 2 * '0' + (m + 1) * '1'
					else:
						out += (ones[i + 1] - ones[i]) * '1'
				elif (ones[i + 1] - ones[i]) % 2 == 0:
					if m < (ones[i + 1] - ones[i]) // 2:
						out += m * '1' + (2 * ((ones[i + 1] - ones[i]) // 2 - m) - 1) * '0' + (m + 1) * '1'
					else:
						out += ((ones[i + 1] - ones[i]) // 2 - 1) * '1' + '0' + (ones[i + 1] - ones[i]) // 2 * '1'
			print(out)
solve()


import sys
readline = sys.stdin.readline
INF = 10 ** 18 + 3
T = int(readline())
Ans = [None] * T
for qu in range(T):
	(N, M) = map(int, readline().split())
	S = list(map(int, readline().strip()))
	one = [-INF]
	for i in range(N):
		if S[i]:
			one.append(i)
	one.append(INF)
	res = [None] * N
	for i in range(N):
		if S[i]:
			res[i] = 1
		ok = 0
		ng = len(one) - 1
		while abs(ok - ng) > 1:
			med = (ok + ng) // 2
			if one[med] <= i:
				ok = med
			else:
				ng = med
		(a, b) = (one[ok], one[ok + 1])
		la = abs(a - i)
		lb = abs(b - i)
		if min(la, lb) <= M and la != lb:
			res[i] = 1
		else:
			res[i] = 0
	Ans[qu] = ''.join(map(str, res))
print('\n'.join(Ans))


def mark(l, l0, n, ma):
	l[n] = 1
	if n > 0:
		if l[n - 1] == 1 and l0[n - 1] != 1:
			l[n - 1] = 0
		else:
			l[n - 1] = 1
	if n < ma - 1:
		l[n + 1] = 1

def go():
	(n, m) = map(int, input().split())
	l = [int(i) for i in input()]
	l1 = [0] * n
	p = l.count(1)
	k = 0
	q = 0
	if p > 0:
		k = l.index(1)
		for i in range(max(0, k - m), k):
			l1[i] = 1
	while p > 1:
		q = k + 1 + l[k + 1:].index(1)
		for i in range(k, min(k + m + 1, q)):
			l1[i] = 1
		for i in range(max(q - m, k + m + 1), q + 1):
			l1[i] = 1
		if k % 2 == q % 2:
			l1[(k + q) // 2] = 0
		k = q
		p -= 1
	if p == 1:
		for i in range(k, min(n, k + m + 1)):
			l1[i] = 1
	s = str()
	for i in l1:
		s += str(i)
	print(s)
for i in range(int(input())):
	go()


for __ in range(int(input())):
	(n, m) = map(int, input().split())
	s = list(input())
	zeros = s.count('0')
	ones = n - zeros
	j = 0
	while j < m and (zeros != n or ones != n):
		indices = []
		flag = True
		for i in range(n):
			if s[i] == '0':
				cnt = 0
				if i > 0 and s[i - 1] == '1':
					cnt += 1
				if i < n - 1 and s[i + 1] == '1':
					cnt += 1
				if cnt == 1:
					indices.append(i)
		for i in indices:
			flag = False
			s[i] = '1'
		if flag:
			break
		j += 1
	print(''.join(s))


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	s = input()
	a = [int(i) for i in s]
	m = min(m, n)
	for _ in range(m):
		b = a[:]
		for (i, num) in enumerate(a):
			if i == 0 and num == 0:
				if a[i + 1] == 1:
					b[i] = 1
			elif i == n - 1 and num == 0:
				if a[i - 1] == 1:
					b[i] = 1
			elif num == 0 and (a[i - 1] == 1 and a[i + 1] == 0 or (a[i + 1] == 1 and a[i - 1] == 0)):
				b[i] = 1
		a = b[:]
	s = ''.join([str(i) for i in a])
	print(s)


import math
import sys
import itertools
import fractions
import copy
wtf = sys.stdin.read()
wtf = wtf.strip().split('\n')
GAP = 2
for t in [wtf[i:i + GAP] for i in range(1, len(wtf), GAP)]:
	(n, m) = map(int, t[0].split())
	S = [x for x in t[1]]
	oids = []
	for i in range(n):
		if S[i] == '1':
			oids.append(i)
	O = len(oids)
	for i in range(O - 1):
		d = abs(oids[i] - oids[i + 1]) - 1
		if d >= 2:
			if d % 2 != 0:
				d -= 1
			dh = d // 2
			if dh >= m:
				S[oids[i] + 1:oids[i] + m + 1] = ['1'] * m
				S[oids[i + 1] - 1:oids[i + 1] - 1 - m:-1] = ['1'] * m
			else:
				S[oids[i] + 1:oids[i] + dh + 1] = ['1'] * dh
				S[oids[i + 1] - 1:oids[i + 1] - 1 - dh:-1] = ['1'] * dh
	if len(oids) > 0:
		k = 0
		for i in range(oids[0] - 1, -1, -1):
			S[i] = '1'
			k += 1
			if k >= m:
				break
		k = 0
		for i in range(oids[-1] + 1, n):
			S[i] = '1'
			k += 1
			if k >= m:
				break
	print(''.join(S))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	word = input()
	word_ = [0] * n
	iteration_count = 0
	for i in range(n):
		word_[i] = int(word[i])
	temp = word_[:]
	for i in range(n):
		count = 0
		for j in range(n):
			if word_[j] == 0:
				if j == 0:
					if j + 1 <= n - 1 and word_[j + 1] == 1:
						temp[j] = 1
						count += 1
				elif j == n - 1:
					if word_[j - 1] == 1:
						temp[j] = 1
						count += 1
				elif word_[j + 1] == 1 and word_[j - 1] == 0:
					temp[j] = 1
					count += 1
				elif word_[j + 1] == 0 and word_[j - 1] == 1:
					temp[j] = 1
					count += 1
		word_ = temp[:]
		iteration_count += 1
		if iteration_count == m:
			break
		if count == 0:
			break
	for i in word_:
		print(i, end='')
	print()


import itertools as it
import functools as ft
import math as mt

def get_input():
	(n, m) = map(int, input().split())
	s = list(input())
	indices = []
	for i in range(n):
		if s[i] == '1':
			indices.append(i)
	return (n, m, s, indices)
testcases = int(input())
while testcases > 0:
	testcases -= 1
	(n, m, s, indices) = get_input()
	if len(indices) == 0:
		pass
	else:
		for i in range(len(indices) - 1):
			steps = min(m, (indices[i + 1] - indices[i] - 1) // 2)
			ones = ['1'] * steps
			s[indices[i] + 1:indices[i] + 1 + steps] = ones
			s[indices[i + 1] - steps:indices[i + 1]] = ones
		steps = min(m, indices[0])
		s[indices[0] - steps:indices[0]] = ['1'] * steps
		steps = min(m, n - indices[-1] - 1)
		s[indices[-1] + 1:indices[-1] + 1 + steps] = ['1'] * steps
	print(''.join(s))


from itertools import *
I = input
for _ in [0] * int(I()):
	m = int(I().split()[1])
	n = len((a := [[*g] for (k, g) in groupby(I())])) - 1
	i = a[0][0] > '0'
	while i <= n:
		x = a[i]
		d = min(m, len(x) >> (0 < i < n))
		if i:
			x[:d] = []
			a[i - 1] += ['1'] * d
		if i < n:
			x[:d] = []
			a[i + 1] += ['1'] * d
		i += 2
	print(''.join(chain(*a)))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = input()
	ar = [0] * (n + 1)
	one = -1
	for i in range(n):
		if s[i] == '1' and one == -1:
			one = i
		elif s[i] == '1' and i - one - 1 <= 2 * m:
			if (i - one) % 2 != 0:
				ar[one] += 1
				ar[i + 1] -= 1
			else:
				ar[one] += 1
				ar[one + int((i - one - 2) / 2) + 1] -= 1
				ar[one + int((i - one - 2) / 2) + 2] += 1
				ar[i + 1] -= 1
			one = i
		elif s[i] == '1':
			ar[one] += 1
			ar[one + m + 1] -= 1
			ar[i - m] += 1
			ar[i + 1] -= 1
			one = i
	for i in range(n):
		if s[i] == '1':
			ar[max(0, i - m)] += 1
			ar[i + 1] -= 1
			break
	for i in range(n - 1, -1, -1):
		if s[i] == '1':
			ar[min(n, i + m + 1)] -= 1
			ar[i] += 1
			break
	for i in range(1, n):
		ar[i] += ar[i - 1]
	for i in range(n):
		if ar[i] >= 1:
			print('1', end='')
		else:
			print('0', end='')
	print('')


from collections import deque

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

def read_ints():
	return map(int, input().split(' '))
t = read_int()
for case_num in range(t):
	(n, m) = read_ints()
	s = input()
	dq = deque()
	alive_day = [-1] * n
	for i in range(n):
		if s[i] == '1':
			dq.append(i)
			alive_day[i] = 0
	while len(dq) > 0:
		i = dq.popleft()
		if alive_day[i] == -1:
			continue
		if alive_day[i] == m:
			break
		if i >= 1:
			if alive_day[i - 1] == -1:
				alive_day[i - 1] = alive_day[i] + 1
				dq.append(i - 1)
			elif alive_day[i - 1] == alive_day[i] + 1:
				alive_day[i - 1] = -1
		if i + 1 < n:
			if alive_day[i + 1] == -1:
				alive_day[i + 1] = alive_day[i] + 1
				dq.append(i + 1)
			elif alive_day[i + 1] == alive_day[i] + 1:
				alive_day[i + 1] = -1
	print(''.join(map(lambda x: '0' if x == -1 else '1', alive_day)))


t = int(input())
for i in range(t):
	a = list(map(int, input().split()))
	c = input()
	n = a[0]
	m = a[1]
	h = []
	k = 0
	p = []
	for j in range(n):
		p.append(m + 1)
		if c[j] == '1':
			h.append(j)
			p[j] = 0
	for j in range(n):
		if k == len(h):
			break
		if c[j] == '0':
			if k == len(h) - 1:
				p[j] = abs(j - h[k])
			else:
				while j > h[k + 1] and k != len(h) - 2:
					k = k + 1
				if h[k] % 2 == 0 and h[k + 1] % 2 == 0 or (h[k] % 2 != 0 and h[k + 1] % 2 != 0):
					if j == (h[k] + h[k + 1]) // 2:
						p[j] = m + 1
						continue
				e = abs(j - h[k])
				f = abs(j - h[k + 1])
				if e > f:
					p[j] = f
				else:
					p[j] = e
	for j in range(n):
		if p[j] <= m:
			print(1, end='')
		else:
			print(0, end='')
	print('')


import sys
import math

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

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

def write(x):
	sys.stdout.write(x)
for i in '.' * int(input()):
	(n, m) = read_ints()
	s = input()
	l = [0]
	for j in s:
		l.append(int(j))
	l.append(0)
	temp = []
	for j in '.' * min(n, m):
		flag = 1
		ch = 1
		while ch <= n:
			if l[ch] == 1:
				ch += 1
				continue
			elif l[ch] == 0 and l[ch - 1] ^ l[ch + 1]:
				temp.append(ch)
				flag = 0
			ch += 1
		for t in temp:
			l[t] = 1
		temp = []
	x = 1
	while x <= n:
		write(str(l[x]))
		x += 1
	print()


import collections
from collections import defaultdict
import math
from math import gcd
from collections import Counter
for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	s = input()
	if '1' not in s or '0' not in s:
		print(s)
		continue
	z = []
	r = s[0]
	for i in range(1, len(s)):
		if s[i] == s[i - 1]:
			r += s[i]
		else:
			z.append(r)
			r = s[i]
	z.append(r)
	ans = ''
	if z[0][0] == '0':
		count = min(len(z[0]), m)
		z[0] = '0' * (len(z[0]) - count) + '1' * count
	ans += z[0]
	for x in z[1:-1]:
		if x[0] != '1':
			l = len(x)
			count = min(l // 2, m)
			temp = '1' * count + '0' * (l - 2 * count) + '1' * count
			ans += temp
		else:
			ans += x
	if z[-1][0] == '0':
		count = min(len(z[-1]), m)
		z[-1] = '1' * count + '0' * (len(z[-1]) - count)
	ans += z[-1]
	print(ans)


import math
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	s = ['0'] + list(str(input())) + ['0']
	a = []
	for j in range(1, n + 1):
		if s[j] == '0':
			a.append(j)
	it = 0
	r = 1
	while it < m and r > 0:
		b = []
		i = 0
		r = 0
		while i < len(a):
			if int(s[a[i] - 1]) + int(s[a[i] + 1]) == 1:
				b.append(a[i])
				del a[i]
				r += 1
			else:
				i += 1
		it += 1
		for i in b:
			s[i] = '1'
	res = ''.join(s)
	print(res[1:len(res) - 1])


T = int(input())
for _ in range(T):
	(n, m) = [int(e) for e in input().split(' ')]
	state = list(input())
	ones = []
	for i in range(len(state)):
		if state[i] == '1':
			ones.append(i)
	last = list(state)
	if len(ones) != 0:
		if state[0] == '0':
			for i in range(ones[0] - 1, max(-1, ones[0] - 1 - m), -1):
				last[i] = '1'
		for i in range(len(ones) - 1):
			if ones[i + 1] - ones[i] > 1:
				(s, e) = (ones[i] + 1, ones[i + 1] - 1)
				count = m
				while s < e and count > 0:
					last[s] = last[e] = '1'
					s += 1
					e -= 1
					count -= 1
		if state[-1] == '0':
			for i in range(ones[-1] + 1, min(len(last), ones[-1] + 1 + m)):
				last[i] = '1'
	print(''.join(last))


def life(n, m, C):
	D = [0] * n
	j = None
	for i in range(n):
		if C[i] == '1':
			if j is None:
				for k in range(max(i - m, 0), i):
					C[k] = '1'
			else:
				d = i - j - 1
				e = min(d // 2, m)
				for k in range(j + 1, j + e + 1):
					C[k] = '1'
				for k in range(i - e, i):
					C[k] = '1'
			j = i
	if j is not None:
		for k in range(j + 1, min(j + m + 1, n)):
			C[k] = '1'
	return C

def main():
	t = readint()
	R = []
	for _ in range(t):
		(n, m) = readinti()
		C = list(input())
		R.append(''.join(life(n, m, C)))
	print('\n'.join(R))
import sys

def readint():
	return int(input())

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

def readintl():
	return list(readinti())

def readintll(k):
	return [readintl() for _ in range(k)]

def log(*args, **kwargs):
	print(*args, **kwargs, file=sys.stderr)
main()


from sys import stdin, stdout
from heapq import heapify, heappush, heappop, heappushpop
from collections import defaultdict as dd, deque as dq, Counter as C
from bisect import bisect_left as bl, bisect_right as br
from itertools import combinations as cmb, permutations as pmb
from math import factorial as f, ceil, gcd, sqrt, log, inf
mi = lambda : map(int, input().split())
ii = lambda : int(input())
li = lambda : list(map(int, input().split()))
mati = lambda r: [li() for _ in range(r)]
lcm = lambda a, b: a * b // gcd(a, b)
MOD = 10 ** 9 + 7

def soe(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def solve():
	(n, m) = mi()
	arr = [x for x in input().strip()]
	ans = True
	while ans and m:
		a2 = False
		s = ['0' for x in range(n)]
		for x in range(n):
			if arr[x] == '0':
				c = 0
				if x > 0 and arr[x - 1] == '1':
					c += 1
				if x < n - 1 and arr[x + 1] == '1':
					c += 1
				if c == 1:
					s[x] = '1'
					a2 = True
			else:
				s[x] = '1'
		arr = s[:]
		m -= 1
		ans = ans and a2
	print(''.join(arr))
for _ in range(ii()):
	solve()


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	x = list(input())
	x1 = x.copy()
	y = 0
	while y != m:
		c = 0
		x = x1.copy()
		y += 1
		for i in range(1, n - 1):
			p = int(x[i - 1])
			q = int(x[i + 1])
			if x[i] == '0' and p ^ q:
				x1[i] = '1'
				c += 1
		if x[-1] == '0' and x[-2] == '1':
			x1[-1] = '1'
			c += 1
		if x[0] == '0' and x[1] == '1':
			x1[0] = '1'
			c += 1
		if c == 0:
			break
	z = ''
	for i in x1:
		z = z + i
	print(z)


import sys
T = int(sys.stdin.readline().strip())
for t in range(0, T):
	(n, m) = list(map(int, sys.stdin.readline().strip().split()))
	s = sys.stdin.readline().strip()
	Z = [0]
	O = []
	v = 0
	for i in range(0, n):
		if int(s[i]) != v:
			v = int(s[i])
			if v == 1:
				O.append(1)
			else:
				Z.append(1)
		elif v == 1:
			O[-1] = O[-1] + 1
		else:
			Z[-1] = Z[-1] + 1
	if len(Z) == len(O):
		Z.append(0)
	if len(O) > 0:
		m0 = min(m, Z[0])
		Z[0] = Z[0] - m0
		O[0] = O[0] + m0
		m0 = min(m, Z[-1])
		Z[-1] = Z[-1] - m0
		O[-1] = O[-1] + m0
	for i in range(1, len(O)):
		m0 = min(m, Z[i] // 2)
		Z[i] = Z[i] - 2 * m0
		O[i] = O[i] + m0
		O[i - 1] = O[i - 1] + m0
	ans = []
	O.append(0)
	for i in range(0, len(O)):
		ans.append('0' * Z[i] + '1' * O[i])
	print(''.join(ans))


import sys
IS_INTERACTIVE = False
input = input
if not IS_INTERACTIVE:
	(*data,) = sys.stdin.read().split('\n')[::-1]

	def input():
		return data.pop()

def fprint(*args, **kwargs):
	print(*args, **kwargs, flush=True)

def eprint(*args, **kwargs):
	print(*args, **kwargs, file=sys.stderr)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(*arr,) = map(int, input())
	changed = True
	while changed and m:
		changed = False
		cpy = arr.copy()
		if arr[0] == 0 and arr[1] == 1:
			cpy[0] = 1
			changed = True
		for i in range(1, n - 1):
			if arr[i] == 0 and arr[i - 1] + arr[i + 1] == 1:
				cpy[i] = 1
				changed = True
		if arr[-1] == 0 and arr[-2] == 1:
			cpy[-1] = 1
			changed = True
		m -= 1
		(arr, cpy) = (cpy, arr)
	print(''.join(map(str, arr)))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	c = list(input())
	s = c.copy()
	for i in range(min(n, m)):
		s = c.copy()
		for j in range(n):
			if j + 1 < n and j - 1 >= 0 and (s[j] == '0'):
				if s[j + 1] == '1' and s[j - 1] == '0' or (s[j + 1] == '0' and s[j - 1] == '1'):
					c[j] = '1'
			elif s[j] == '0' and j - 1 >= 0:
				if s[j - 1] == '1':
					c[j] = '1'
			elif s[j] == '0' and j + 1 < n:
				if s[j + 1] == '1':
					c[j] = '1'
	print(''.join(c))


def fun(ls, lt):
	(n, k) = lt
	ans = ''
	count0 = 0
	count1 = 0
	first_zeros = 0
	for i in ls:
		if i == '0':
			count0 += 1
		else:
			if count1 == 0:
				first_zeros = count0
				count0 = 0
			else:
				ans += '1'
				if count0 % 2 == 0:
					if count0 > 2 * k:
						ans += '1' * k + (count0 - 2 * k) * '0' + '1' * k
					else:
						ans += '1' * count0
					count0 = 0
				else:
					if count0 > 2 * k:
						ans += '1' * k + (count0 - 2 * k) * '0' + '1' * k
					else:
						ans += '1' * (count0 // 2) + '0' + '1' * (count0 // 2)
					count0 = 0
			count1 += 1
	if count1 > 0:
		if count0 == 0:
			ans += '1'
		elif k >= count0:
			ans += '1' + '1' * count0
		else:
			ans += '1' + '1' * k + '0' * (count0 - k)
		if k >= first_zeros:
			ans = '1' * first_zeros + ans
		else:
			ans = '0' * (first_zeros - k) + '1' * k + ans
	else:
		print('0' * count0)
		return
	print(ans)
T = int(input())
for _ in range(T):
	lt = list(map(int, input().split()))
	st = input()
	fun(st, lt)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = input()
	a = [0] * n
	left = 10 ** 18 + 1
	right = 0
	for i in range(n):
		if s[i] == '1':
			a[i] = '1'
			right = i
			if left == 10 ** 18 + 1:
				x = 0
			else:
				x = left + 1
			for j in range(x, right):
				a[j] = [left, right]
			left = right
	if left == 10 ** 18 + 1:
		x = 0
	else:
		x = left + 1
	for j in range(x, n):
		a[j] = [left, 10 ** 18 + 1]
	ans = ''
	for i in range(n):
		if a[i] == '1':
			ans += '1'
		else:
			(dist1, dist2) = (abs(a[i][0] - i), abs(a[i][1] - i))
			if dist2 == dist1:
				ans += '0'
			elif min(dist1, dist2) <= m:
				ans += '1'
			else:
				ans += '0'
	print(ans)


t = int(input())
while t:
	t -= 1
	(n, m) = map(int, input().split())
	s = input()
	ans = []
	i = 0
	while i < n and s[i] == '0':
		i += 1
		ans.append(0)
	if i == n:
		print(s)
	else:
		k = min(i, m)
		while k:
			ans[i - k] = 1
			k -= 1
		j = i
		ans.append(ord(s[i]) - 48)
		i += 1
		while i < n:
			ans.append(ord(s[i]) - 48)
			if s[i] != s[i - 1]:
				if s[i - 1] == '0':
					k = min((i - j - 1) // 2, m)
					while k:
						ans[i - k] = '1'
						ans[j + k] = '1'
						k -= 1
				else:
					j = i - 1
			i += 1
		if s[i - 1] == '0':
			k = min(i - j - 1, m)
			while k:
				ans[j + k] = '1'
				k -= 1
		for x in ans:
			print(x, end='')
		print()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = input()
	if m > n:
		m = n
	for _ in range(m):
		temp = ''
		if s[0] == '1':
			temp += '1'
		elif s[1] == '1':
			temp += '1'
		else:
			temp += '0'
		for j in range(1, n - 1):
			if s[j] == '1':
				temp += '1'
			elif ord(s[j - 1]) - ord('0') + ord(s[j + 1]) - ord('0') == 1:
				temp += '1'
			else:
				temp += '0'
		if s[n - 1] == '1':
			temp += '1'
		elif s[n - 2] == '1':
			temp += '1'
		else:
			temp += '0'
		s = temp
	print(s)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	k = min(n, k)
	s = list(input())
	old = ['0'] + s + ['0']
	new = old[:]
	for times in range(k):
		for i in range(1, n + 1):
			if old[i] == '0':
				if old[i - 1] == '0' and old[i + 1] == '1' or (old[i - 1] == '1' and old[i + 1] == '0'):
					new[i] = '1'
		old = new[:]
	print(''.join(new[1:i + 1]))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def main():
	pass

def binary(n):
	return bin(n).replace('0b', '')

def decimal(s):
	return int(s, 2)

def pow2(n):
	p = 0
	while n > 1:
		n //= 2
		p += 1
	return p

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

def lts(l):
	s = ''.join(map(str, l))
	return s

def stl(s):
	l = list(s)
	return l

def sq(a, target, arr=[]):
	s = sum(arr)
	if s == target:
		return arr
	if s >= target:
		return
	for i in range(len(a)):
		n = a[i]
		remaining = a[i + 1:]
		ans = sq(remaining, target, arr + [n])
		if ans:
			return ans

def SieveOfEratosthenes(n):
	cnt = 0
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n + 1):
		if prime[p]:
			cnt += 1
	return cnt

def nCr(n, r):
	f = math.factorial
	return f(n) // f(r) // f(n - r)
mod = int(1000000000.0) + 7

def ssinp():
	return input()

def iinp():
	return int(input())

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

def llinp():
	return list(map(int, input().split()))

def p(xyz):
	print(xyz)

def p2(a, b):
	print(a, b)
import math
for __ in range(iinp()):
	(n, m) = nninp()
	temp = list(ssinp())
	for i in range(min(n, m)):
		a = temp.copy()
		for j in range(n):
			if j == 0:
				if a[0] == '0' and a[1] == '1':
					temp[0] = '1'
			elif j == n - 1:
				if a[n - 1] == '0' and a[n - 2] == '1':
					temp[n - 1] = '1'
			elif a[j] == '0':
				if a[j - 1] == '1' and a[j + 1] == '0' or (a[j - 1] == '0' and a[j + 1] == '1'):
					temp[j] = '1'
	print(lts(temp))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	x = input()
	for i in range(min(n, m)):
		while '101' in x:
			x = x.replace('101', '1_1')
		x = x.replace('10', '11')
		x = x.replace('01', '11')
	x = x.replace('_', '0')
	print(x)


from collections import defaultdict, deque
from heapq import heappush, heappop
from math import inf
ri = lambda : map(int, input().split())
ro = lambda : int(input())

def solve():
	(n, m) = ri()
	A = list(input())
	q = deque()
	for i in range(n):
		if A[i] == '1':
			q.append(i)
	while q and m:
		new = A[:]
		for _ in range(len(q)):
			idx = q.popleft()
			if idx - 1 >= 0 and A[idx - 1] == '0':
				left = idx - 1
				valid = True
				if left - 1 >= 0 and A[left - 1] == '1':
					valid = False
				if valid:
					q.append(left)
					new[left] = '1'
			if idx + 1 < n and A[idx + 1] == '0':
				right = idx + 1
				valid = True
				if right + 1 < n and A[right + 1] == '1':
					valid = False
				if valid:
					q.append(right)
					new[right] = '1'
		A = new
		m -= 1
	print(''.join(A))
t = 1
t = int(input())
while t:
	t -= 1
	solve()


t = int(input())
for _ in range(t):
	(n, m) = [int(x) for x in input().split()]
	a = list(input())
	i = 0
	l = -1
	while i < n:
		zeroes = 0
		while i < n and a[i] == '0':
			i += 1
			zeroes += 1
		h = min(m, zeroes >> 1)
		if l != -1:
			for j in range(l, l + h if i < n else min(n, l + m)):
				a[j] = '1'
		if i < n:
			for j in range(i - h if l != -1 else max(0, i - m), i):
				a[j] = '1'
		while i < n and a[i] == '1':
			i += 1
		l = i
	print(''.join(a))


from sys import stdin
t = int(stdin.readline())
for _ in range(t):
	(n, m) = map(int, stdin.readline().split())
	m = min(n, m)
	a = list(stdin.readline()[:-1])
	a = ['0'] + a + ['0']
	new = a[:]
	for i in range(m):
		for j in range(1, n + 1):
			if a[j] == '0':
				if a[j - 1] == '0' and a[j + 1] == '1' or (a[j - 1] == '1' and a[j + 1] == '0'):
					new[j] = '1'
		a = new[:]
	print(''.join(new[1:n + 1]))


import math, sys, heapq
for t in range(int(input())):
	(n, m) = map(int, input().split())
	s = list(input())
	if '1' not in s or '0' not in s:
		print(*s, sep='')
		continue
	a = []
	for i in range(n):
		if s[i] == '1':
			a.append(i)
	c = 0
	for i in range(a[0] - 1, -1, -1):
		if c == m:
			break
		s[i] = '1'
		c += 1
	c = 0
	for i in range(a[len(a) - 1] + 1, n):
		if c == m:
			break
		s[i] = '1'
		c += 1
	for i in range(len(a) - 1):
		x = a[i] + 1
		y = a[i + 1] - 1
		for i in range(m):
			if x >= y:
				break
			s[x] = '1'
			s[y] = '1'
			x += 1
			y -= 1
	print(*s, sep='')


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def main():
	ref = int(input())
	for z in range(ref):
		nt = list(map(int, input().rstrip().split()))
		t = nt[1]
		n = nt[0]
		st = list(input())
		st1 = set()
		st0 = set()
		for i in range(n):
			if st[i] == '1':
				st1.add(i)
			elif st[i] == '0':
				st0.add(i)
		st1set = st1
		st0set = st0
		if len(st1set) != 0:
			for z in range(t):
				rem = []
				for i in st0set:
					if i - 1 in st1set and i + 1 not in st1set or (i + 1 in st1set and i - 1 not in st1set):
						rem.append(i)
				active = True
				for i in rem:
					active = False
					st0set.discard(i)
					st1set.add(i)
				if active:
					break
		final = [' '] * n
		for i in st1set:
			final[i] = '1'
		for i in st0set:
			final[i] = '0'
		print(''.join(final))
main()


import os
import sys
from io import BytesIO, IOBase
from collections import Counter
import math as mt
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def lcm(a, b):
	return a * b / gcd(a, b)
mod = int(1000000000.0) + 7

def power(k, n):
	if n == 0:
		return 1
	if n % 2:
		return power(k, n - 1) * k % mod
	t = power(k, n // 2)
	return t * t % mod

def totalPrimeFactors(n):
	count = 0
	if n % 2 == 0:
		count += 1
		while n % 2 == 0:
			n //= 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			count += 1
			while n % i == 0:
				n //= i
		i += 2
	if n > 2:
		count += 1
	return count

def main():
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		S = input()
		s = []
		for i in S:
			if i == '0' or i == '1':
				s.append(int(i))
		while m > 0:
			f = 0
			t = []
			for i in range(n):
				if s[i] == 0:
					if i == 0:
						if s[1] == 1:
							t.append(1)
							f = 1
						else:
							t.append(0)
					elif i == n - 1:
						if s[n - 2] == 1:
							t.append(1)
							f = 1
						else:
							t.append(0)
					elif s[i - 1] + s[i + 1] == 1:
						t.append(1)
						f = 1
					else:
						t.append(0)
				else:
					t.append(1)
			if f == 0:
				break
			s = []
			for i in t:
				s.append(i)
			m -= 1
		for i in s:
			print(i, end='')
		print('')
	return
main()


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	old = list(input())
	lft = [0] * n
	rht = [0] * n
	flag = 0
	for i in range(n):
		if old[i] == '1':
			lft[i] = 0
			flag = 1
		elif flag == 1:
			lft[i] = lft[i - 1] + 1
	flag = 0
	for i in range(n - 1, -1, -1):
		if old[i] == '1':
			rht[i] = 0
			flag = 1
		elif flag == 1:
			rht[i] = rht[i + 1] + 1
	res = ['0'] * n
	for i in range(n):
		if lft[i] == rht[i] and old[i] == '0':
			res[i] = '0'
		elif lft[i] == 0 and rht[i] == 0 and (old[i] == '1'):
			res[i] = '1'
		else:
			if lft[i] == 0 or rht[i] == 0:
				mi = max(lft[i], rht[i])
			else:
				mi = min(lft[i], rht[i])
			if mi <= m:
				res[i] = '1'
			else:
				res[i] = '0'
	ans = ''
	for i in range(n):
		ans += res[i]
	print(ans)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = list(input())
	first_1 = True
	i = 0
	while i < n:
		if a[i] == '1':
			if first_1 == True:
				first_1 = False
				k = i - 1
				temp_m = m
				while k >= 0 and temp_m > 0:
					a[k] = '1'
					k -= 1
					temp_m -= 1
			else:
				j = i + 1
				while j < n:
					if a[j] == '1':
						temp_j = j
						temp_m = m
						while j > i + 2 and temp_m > 0:
							temp_m -= 1
							i += 1
							j -= 1
							a[i] = '1'
							a[j] = '1'
						i = temp_j
						break
					else:
						j += 1
				if j == n:
					k = i + 1
					temp_m = m
					while k < n and temp_m > 0:
						a[k] = '1'
						k += 1
						temp_m -= 1
					i = n
		else:
			i += 1
	str1 = ''
	print(str1.join(a))


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	st = list(input())
	d = {}
	l = -1
	r = -1
	for i in range(n):
		if st[i] == '0':
			d[i] = [l]
		else:
			l = i
	for i in range(n - 1, -1, -1):
		if st[i] == '0':
			d[i].append(r)
		else:
			r = i
	for k in d:
		if d[k][0] == -1 and d[k][1] == -1:
			continue
		elif d[k][0] == -1 or d[k][1] == -1:
			if abs(k - (d[k][0] + d[k][1] + 1)) <= m:
				st[k] = '1'
		elif abs(k - d[k][0]) == abs(k - d[k][1]):
			continue
		elif abs(k - d[k][0]) <= m or abs(k - d[k][1]) <= m:
			st[k] = '1'
	print(''.join(st))


t = int(input())
for _ in range(t):
	(n, m) = [int(d) for d in input().split()]
	s = list(input())
	idx = []
	for i in range(len(s)):
		if s[i] == '1':
			idx.append(i)
	if idx != []:
		if idx[0] > 0:
			l = idx[0]
			c = 0
			while c < min(l, m):
				s[l - c - 1] = '1'
				c = c + 1
		for i in range(len(idx) - 1):
			l = idx[i]
			r = idx[i + 1]
			c = 0
			while c < min((r - l - 1) // 2, m):
				s[l + c + 1] = '1'
				s[r - c - 1] = '1'
				c = c + 1
		if idx[-1] < n - 1:
			c = 0
			l = idx[-1]
			while c < min(m, n - 1 - l):
				s[l + c + 1] = '1'
				c = c + 1
	print(''.join(s))


for t in range(int(input())):
	line = input().split()
	(n, m) = (int(line[0]), int(line[1]))
	line = input()
	s = ''
	c = 0
	i = 0
	while i < n and c < n:
		if line[i] == '1':
			if c % 2 == 1:
				if c == i:
					if c <= m:
						s += '1' * (c + 1)
						c = 0
					else:
						s += '0' * (c - m)
						s += '1' * (m + 1)
						c = 0
				elif c <= 2 * m + 1:
					s += '1' * (c // 2)
					s += '0'
					s += '1' * (c // 2 + 1)
					c = 0
				else:
					s += '1' * m
					s += '0' * (c - 2 * m)
					s += '1' * (m + 1)
					c = 0
			elif c == i:
				if c <= m:
					s += '1' * (c + 1)
					c = 0
				else:
					s += '0' * (c - m)
					s += '1' * (m + 1)
					c = 0
			elif c <= 2 * m:
				s += '1' * (c + 1)
				c = 0
			else:
				s += '1' * m
				s += '0' * (c - 2 * m)
				s += '1' * (m + 1)
				c = 0
		else:
			c += 1
		i += 1
	if c != 0:
		if c < n:
			if c <= m:
				s += '1' * c
			else:
				s += '1' * m
				s += '0' * (c - m)
		else:
			s += '0' * c
	print(s)


def sol():
	(n, m) = [int(x) for x in input().split()]
	arr = list(input())
	jedynki = []
	ile = 0
	for i in range(n):
		if int(arr[i]):
			jedynki.append(i)
			ile += 1
	for i in range(ile - 1):
		p = jedynki[i]
		q = jedynki[i + 1]
		x = m
		while p + 1 != q - 1 and x and (p != q + 1):
			p += 1
			q -= 1
			arr[p] = '1'
			arr[q] = '1'
			x -= 1
	if ile > 0:
		if jedynki[-1] != n - 1:
			ind = jedynki[-1] + 1
			x = m
			while x and ind < n:
				arr[ind] = '1'
				ind += 1
				x -= 1
		if jedynki[0] != 0:
			ind = jedynki[0] - 1
			x = m
			while x and ind > -1:
				arr[ind] = '1'
				ind -= 1
				x -= 1
	print(''.join(arr))

def main():
	for i in range(int(input())):
		sol()
main()


from os import rename

def game(n, m, k):
	k = list(k)
	ones = []
	ans = [0] * n
	count = 0
	for j in range(n):
		if k[j] == '1':
			ones.append(j)
	if len(ones) == 0:
		for done in range(len(k)):
			print(k[done], end='')
		return
	if ones[0] > 0:
		if ones[0] <= m:
			for one_start in range(0, ones[0]):
				k[one_start] = '1'
		if ones[0] > m:
			for one_startless in range(ones[0] - 1, ones[0] - m - 1, -1):
				k[one_startless] = '1'
	for i in range(0, len(ones) - 1):
		check = ones[i + 1] - ones[i] - 1
		if check > 0 and check % 2 == 0:
			if check // 2 < m:
				for even_1 in range(ones[i], ones[i + 1]):
					k[even_1] = '1'
			elif check // 2 >= m:
				for even_1less in range(ones[i], ones[i] + m + 1):
					k[even_1less] = '1'
				for even_1more in range(ones[i + 1] - 1, ones[i + 1] - m - 1, -1):
					k[even_1more] = '1'
		if check > 0 and check % 2 != 0:
			if check // 2 <= m:
				for odd_1 in range(ones[i] + 1, ones[i + 1]):
					if odd_1 == (ones[i + 1] + ones[i]) // 2:
						k[odd_1] = '0'
					else:
						k[odd_1] = '1'
			elif check // 2 > m:
				for odd_1more in range(ones[i] + 1, ones[i] + m + 1):
					k[odd_1more] = '1'
				for odd_1less in range(ones[i + 1] - 1, ones[i + 1] - m - 1, -1):
					k[odd_1less] = '1'
	if ones[-1] < n:
		if n - ones[-1] - 1 <= m:
			for one_last in range(ones[-1], n):
				k[one_last] = '1'
		elif n - ones[-1] > m:
			for one_lastless in range(ones[-1] + 1, ones[-1] + m + 1):
				k[one_lastless] = '1'
	for fin in range(len(k)):
		print(k[fin], end='')
	return
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	k = input()
	game(n, m, k)
	print()


I = input
r = str.replace
for _ in [0] * int(I()):
	(n, m) = map(int, I().split())
	s = '0' + I() + '0'
	for _ in [0] * min(m, n):
		s = r(r(r(r(r(s, '100', '1*0'), '001', '0*1'), '*01', '111'), '10*', '111'), '*', '1')
	print(s[1:-1])


for i in range(int(input())):
	(n, m) = map(int, input().split())
	t = list(input())
	if t.count('1') == 0:
		print(''.join(t))
	else:
		while m:
			h = 0
			f = []
			for i in range(len(t)):
				if t[i] == '0':
					left = 0
					right = 0
					if i - 1 >= 0:
						if t[i - 1] == '1':
							left = 1
					if i + 1 < len(t):
						if t[i + 1] == '1':
							right = 1
					if left + right == 1:
						h += 1
						f.append(i)
			if len(f) == 0:
				break
			for j in f:
				t[j] = '1'
			m -= 1
		print(''.join(t))


import copy
for i in range(int(input())):
	(n, m) = map(int, input().split())
	s = input()
	S = list(s)
	c = 1
	flag = 1
	A = copy.deepcopy(S)
	x = m
	if n < m:
		x = n
	while c <= x and flag:
		flag = 0
		if S[1] == '1':
			if A[0] != '1':
				A[0] = '1'
				flag = 1
		for j in range(1, n - 1):
			if S[j - 1] == '1' and S[j + 1] == '0' or (S[j - 1] == '0' and S[j + 1] == '1'):
				if A[j] != 1:
					A[j] = '1'
					flag = 1
		if S[n - 2] == '1':
			if A[n - 1] != '1':
				A[n - 1] = '1'
				flag = 1
		c += 1
		S = copy.deepcopy(A)
	s1 = ''.join(S)
	print(s1)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	l = list(input())
	poz = []
	for x in range(0, n):
		if l[x] == '1':
			poz.append(x)
			for xx in range(x - 1, max(x - m - 1, -1), -1):
				if l[xx] == '1' or l[xx] == '2':
					break
				l[xx] = '2'
			for xx in range(x + 1, x + m + 1, +1):
				if xx == n or l[xx] == '1' or l[xx] == '2':
					break
				l[xx] = '2'
	for xx in range(0, len(poz) - 1):
		if (poz[xx] + poz[xx + 1]) % 2 == 0 and l[(poz[xx] + poz[xx + 1]) // 2] != '0':
			l[(poz[xx] + poz[xx + 1]) // 2] = '0'
	s_l = ''.join(l).replace('2', '1')
	print(s_l)


import heapq
import sys
from math import *
import threading
from heapq import *
from itertools import count
from pprint import pprint
from collections import defaultdict
from heapq import heapify, heappop, heappush
sys.setrecursionlimit(300000)
mod = 10 ** 9 + 7
inf = 10 ** 15
decision = ['NO', 'YES']
yes = 'YES'
no = 'NO'
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def npr(n, r):
	return factorial(n) % mod // (factorial(n - r) % mod) if n >= r else 0

def ncr(n, r):
	return factorial(n) % mod // (factorial(r) % mod * (factorial(n - r) % mod)) if n >= r else 0

def lower_bound(li, num):
	answer = -1
	start = 0
	end = len(li) - 1
	while start <= end:
		middle = (end + start) // 2
		if li[middle] >= num:
			answer = middle
			end = middle - 1
		else:
			start = middle + 1
	return answer

def upper_bound(li, num):
	answer = -1
	start = 0
	end = len(li) - 1
	while start <= end:
		middle = (end + start) // 2
		if li[middle] <= num:
			answer = middle
			start = middle + 1
		else:
			end = middle - 1
	return answer

def abs(x):
	return x if x >= 0 else -x

def binary_search(li, val):
	ans = -1
	lb = 0
	ub = len(li) - 1
	while lb <= ub:
		mid = (lb + ub) // 2
		if li[mid] > val:
			ub = mid - 1
		elif val > li[mid]:
			lb = mid + 1
		else:
			ans = mid
			break
	return ans

def kadane(x):
	sum_so_far = 0
	current_sum = 0
	for i in x:
		current_sum += i
		if current_sum < 0:
			current_sum = 0
		else:
			sum_so_far = max(sum_so_far, current_sum)
	return sum_so_far

def pref(li):
	pref_sum = [0]
	for i in li:
		pref_sum.append(pref_sum[-1] + i)
	return pref_sum

def SieveOfEratosthenes(n):
	prime = [{1, i} for i in range(n + 1)]
	p = 2
	while p <= n:
		for i in range(p * 2, n + 1, p):
			prime[i].add(p)
		p += 1
	return prime

def primefactors(n):
	factors = []
	while n % 2 == 0:
		factors.append(2)
		n //= 2
	for i in range(3, int(sqrt(n)) + 1, 2):
		while n % i == 0:
			factors.append(i)
			n //= i
	if n > 2:
		factors.append(n)
	return factors

def prod(li):
	ans = 1
	for i in li:
		ans *= i
	return ans

def sumk(a, b):
	print('called for', a, b)
	ans = a * (a + 1) // 2
	ans -= b * (b + 1) // 2
	return ans

def sumi(n):
	ans = 0
	if len(n) > 1:
		for x in n:
			ans += int(x)
		return ans
	else:
		return int(n)

def checkwin(x, a):
	if a[0][0] == a[1][1] == a[2][2] == x:
		return 1
	if a[0][2] == a[1][1] == a[2][0] == x:
		return 1
	if len(set(a[0])) == 1 and a[0][0] == x or (len(set(a[1])) == 1 and a[1][0] == x) or (len(set(a[2])) == 1 and a[2][0] == x):
		return 1
	if len(set(a[0][:])) == 1 and a[0][0] == x or (len(set(a[1][:])) == 1 and a[0][1] == x) or (len(set(a[2][:])) == 1 and a[0][0] == x):
		return 1
	return 0
karmanya = int(input())
while karmanya != 0:
	karmanya -= 1
	(n, m) = map(int, input().split())
	a = [int(x) for x in input()]
	if len(set(a)) == 1 and a[0] == 0:
		print('0' * n)
		continue
	ind = a.index(1)
	b = [0] * n
	cnt = 0
	b[ind] = 1
	for i in range(ind - 1, -1, -1):
		if cnt == m:
			break
		b[i] = 1
		cnt += 1
	for i in range(ind + 1, n):
		if a[i] == 1:
			b[i] = 1
			zer = i - ind - 1
			steps = min(zer // 2, m)
			for j in range(ind + 1, ind + steps + 1):
				b[j] = 1
			for j in range(i - 1, i - steps - 1, -1):
				b[j] = 1
			ind = i
	for i in range(ind, min(ind + m + 1, n)):
		b[i] = 1
	print(''.join((str(x) for x in b)))


t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	s = input()
	prefix = []
	suffix = []
	cur_left = float('-inf')
	for i in range(len(s)):
		prefix.append(cur_left)
		if s[i] == '1':
			cur_left = i
	cur_right = float('inf')
	for i in range(len(s) - 1, -1, -1):
		suffix.append(cur_right)
		if s[i] == '1':
			cur_right = i
	suffix.reverse()
	answer = []
	for i in range(len(s)):
		left_dist = i - prefix[i]
		right_dist = suffix[i] - i
		if s[i] == '0' and left_dist != right_dist and (min(left_dist, right_dist) <= m):
			answer.append('1')
		else:
			answer.append(s[i])
	print(''.join(answer))


import re
I = input
r = re.sub
for _ in [0] * int(I()):
	m = min(map(int, I().split()))
	s = f'0{I()}0'
	while m:
		m -= 1
		s = r('#', '1', r('(?<=0)0(?=1)|(?<=1)0(?=0)', '#', s))
	print(s[1:-1])


import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	S = input().rstrip()
	last_ones = [float('-inf')]
	for i in range(1, len(S)):
		last_ones.append(i - 1 if S[i - 1] == '1' else last_ones[-1])
	next_ones = [float('inf')]
	for i in range(len(S) - 2, -1, -1):
		next_ones.append(i + 1 if S[i + 1] == '1' else next_ones[-1])
	next_ones.reverse()
	ans = []
	for (i, x) in enumerate(S):
		if x == '1':
			ans.append('1')
			continue
		f_delta = next_ones[i] - i
		s_delta = i - last_ones[i]
		if f_delta != s_delta and min(f_delta, s_delta) <= M:
			ans.append('1')
		else:
			ans.append('0')
	print(''.join(ans))


import bisect

def solve(nm, s):
	n = nm[0]
	m = nm[1]
	arr_1 = []
	for i in range(n):
		if s[i] == '1':
			arr_1.append(i)
	if len(arr_1) == 0:
		return s
	arr_1.sort()
	arr = []
	for i in range(n):
		if s[i] == '0':
			ind = bisect.bisect(arr_1, i)
			if ind == 0:
				if arr_1[ind] - i <= m:
					s = s[:i] + '1' + s[i + 1:]
			elif ind == len(arr_1):
				if i - arr_1[ind - 1] <= m:
					s = s[:i] + '1' + s[i + 1:]
			else:
				len1 = i - arr_1[ind - 1]
				len2 = arr_1[ind] - i
				if len1 == len2:
					continue
				elif min(len1, len2) <= m:
					s = s[:i] + '1' + s[i + 1:]
	return s
t = int(input())
for i in range(t):
	nm = list(map(int, input().strip().split()))[:2]
	s = input()
	print(solve(nm, s))


import copy

def up(s):
	s = '0' + s + '0'
	scp = ''
	for i in range(1, len(s) - 1):
		if s[i - 1] != s[i + 1]:
			scp = scp + '1'
		else:
			scp = scp + s[i]
	return scp

def slove():
	ip1 = input().split()
	n = int(ip1[0])
	m = int(ip1[1])
	m = min(m, n)
	s = str(input())
	for i in range(m):
		s = up(s)
	print(s)
t = int(input())
for i in range(t):
	slove()


for i in range(int(input())):
	(n, m) = [int(i) for i in input().split()]
	arr = input()
	if arr.count('0') == 0 or arr.count('1') == 0:
		print(arr)
		continue
	opt = ''
	for i in range(m):
		for (i, b) in enumerate(arr):
			if i == 0:
				a = '0'
				c = arr[i + 1]
			elif i == n - 1:
				a = arr[i - 1]
				c = '0'
			else:
				a = arr[i - 1]
				c = arr[i + 1]
			if a == '0' and c == '0' or (a == '1' and c == '1'):
				opt += b
			else:
				opt += '1'
		if arr == opt:
			break
		else:
			arr = opt
			opt = ''
	print(arr)


for t in range(int(input())):
	(n, l) = map(int, input().split())
	s = input()
	while l > 0 and ('10' in s or '01' in s):
		while '101' in s:
			s = s.replace('101', '1_1')
		s = s.replace('10', '11')
		s = s.replace('01', '11')
		l -= 1
	s = s.replace('_', '0')
	print(s)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	s = input().strip()
	s_1 = [len(k) for k in s.split('1')]
	s_2 = s_1.copy()
	z = len(s_1)
	if z == 1:
		print(s)
	else:
		s_2[0] = max(0, s_1[0] - m)
		s_2[-1] = max(0, s_1[-1] - m)
		for i in range(1, z - 1):
			s_2[i] = max(s_1[i] % 2, s_1[i] - 2 * m)
		r = '0' * s_2[0] + '1' * (s_1[0] - s_2[0])
		for i in range(1, z - 1):
			x = (s_1[i] - s_2[i]) // 2
			r += '1' * (x + 1) + '0' * s_2[i] + '1' * x
		r += '1' * (1 + s_1[-1] - s_2[-1]) + '0' * s_2[-1]
		print(r)


from itertools import combinations, product
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	s = input()
	ones = []
	res = []
	for i in range(n):
		if s[i] == '1':
			ones.append(i)
	L_ones = len(ones)
	if L_ones == 0 or m == 0:
		print(s)
		continue
	x = 0
	for i in range(n):
		if s[i] == '1':
			print('1', end='')
			continue
		while True:
			if x < L_ones and ones[x] < i:
				x += 1
			else:
				break
		if x == 0:
			if ones[x] - i <= m:
				print('1', end='')
			else:
				print('0', end='')
		elif x == L_ones:
			if i - ones[-1] <= m:
				print('1', end='')
			else:
				print('0', end='')
		elif min(i - ones[x - 1], ones[x] - i) != max(i - ones[x - 1], ones[x] - i) and min(i - ones[x - 1], ones[x] - i) <= m:
			print('1', end='')
		else:
			print('0', end='')
	print()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = input()
	left = [m + 1] * len(s)
	right = [m + 1] * len(s)
	current = -1 * (m + len(s) + 2)
	for i in range(len(s)):
		if s[i] == '0':
			left[i] = min(left[i], i - current)
		else:
			current = i
	current = m + len(s) + 2
	for i in reversed(range(len(s))):
		if s[i] == '0':
			right[i] = min(right[i], current - i)
		else:
			current = i
	output = list(s)
	for i in range(len(s)):
		if s[i] == '0' and (left[i] <= m or right[i] <= m) and (left[i] != right[i]):
			output[i] = '1'
	print(*output, sep='')


def game_of_life(alive, n, m):
	alive = list(alive)
	for i in range(m):
		to_live = []
		for j in range(n):
			if alive[j] == '0':
				if j > 0 and alive[j - 1] == '1' or (j < n - 1 and alive[j + 1] == '1'):
					if not ((j > 0 and alive[j - 1] == '1') and (j < n - 1 and alive[j + 1] == '1')):
						to_live.append(j)
		if not to_live:
			return ''.join(alive)
		for j in to_live:
			alive[j] = '1'
	return ''.join(alive)
T = int(input())
for t in range(T):
	(n, m) = map(int, input().split())
	print(game_of_life(input(), n, m))


import sys
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	s = list(input())
	left = [0] * n
	right = [0] * n
	c = 0
	pos = sys.maxsize
	for i in range(n):
		if s[i] == '1':
			pos = 0
			continue
		if pos == sys.maxsize:
			left[i] = sys.maxsize
		else:
			pos += 1
			left[i] = pos
	pos = sys.maxsize
	for i in range(n - 1, -1, -1):
		if s[i] == '1':
			pos = 0
			continue
		if pos == sys.maxsize:
			right[i] = sys.maxsize
		else:
			pos += 1
			right[i] = pos
	for i in range(n):
		if s[i] == '0':
			if min(left[i], right[i]) <= m and left[i] != right[i]:
				s[i] = '1'
	print(''.join(s))


from collections import defaultdict, deque, Counter
from sys import stdin, stdout
from heapq import heappush, heappop
import math
import io
import os
import math
import bisect

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def digits(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def ceil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def mapin():
	return map(int, input().split())
t = int(input())
for _ in range(t):
	(n, m) = mapin()
	l = list(input())
	s = ['0'] * n
	ch = 0
	for i in range(m):
		ch = 0
		for j in range(n):
			s[j] = l[j]
		if l[0] == '0':
			if l[1] == '1':
				s[0] = '1'
				ch = 1
		for j in range(1, n - 1):
			if l[j] == '0':
				if l[j + 1] != l[j - 1]:
					s[j] = '1'
					ch = 1
		if l[-1] == '0':
			if l[-2] == '1':
				s[-1] = '1'
				ch = 1
		for j in range(n):
			l[j] = s[j]
		if ch == 0:
			break
	print(''.join(l))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = input()
	l = []
	p = []
	b = 0
	k = 0
	for i in range(n):
		if s[i] == '1':
			l.append(1)
			p.append(i)
			b += 1
		else:
			l.append(0)
	if b != 0:
		for i in range(b - 1):
			x = p[i]
			y = p[i + 1]
			j = min((y - x - 1) // 2, m)
			while j:
				l[x + j] = 1
				l[y - j] = 1
				j -= 1
		for i in range(1, m + 1):
			if i > p[0]:
				break
			l[p[0] - i] = 1
		for i in range(1, m + 1):
			if p[b - 1] + i >= n:
				break
			l[p[b - 1] + i] = 1
	for i in l:
		print(i, end='')
	print()


from io import BytesIO, IOBase
import sys
import math
import os
import heapq
from collections import defaultdict, deque
from math import ceil
from bisect import bisect_left, bisect_left
from time import perf_counter
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

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

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

def mfloat():
	return map(float, input().split())

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

def solve():
	(n, k) = mint()
	a = list(map(int, input()))
	for i in range(min(n - 1, k)):
		copy = [0] * n
		for i in range(n):
			if a[i] == 1:
				copy[i] = 1
			else:
				total = (a[i - 1] if i else 0) + (a[i + 1] if i + 1 < n else 0)
				if total == 1:
					copy[i] = 1
		a = copy
	print(*a, sep='')

def main():
	t = int(input())
	for _ in range(t):
		solve()
start_time = perf_counter()
main()
print(perf_counter() - start_time, file=sys.stderr)


for _ in range(0, int(input())):
	(n, m) = map(int, input().split())
	s = input()
	for i in range(0, min(n, m)):
		x = 1
		while '101' in s:
			s = s.replace('101', '1x1')
		s = s.replace('10', '11')
		s = s.replace('01', '11')
		s = s.replace('x', '0')
	print(s)


from collections import deque, defaultdict
from math import sqrt, ceil, factorial, floor, inf, log2, sqrt, gcd
import bisect
import copy
from itertools import combinations
import sys

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

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

def input():
	return sys.stdin.readline().strip()
for _ in range(int(input())):
	(n, m) = get_ints()
	s = input()
	li = [str(x) for x in s]
	tot = min(n, m)
	for i in range(tot):
		lii = []
		for j in range(len(s)):
			if j == 0:
				if li[j + 1] == '1':
					lii.append(j)
			if j == n - 1:
				if li[j - 1] == '1':
					lii.append(j)
			if j != 0 and j != n - 1:
				if li[j - 1] == '1' and li[j + 1] == '0' or (li[j - 1] == '0' and li[j + 1] == '1'):
					lii.append(j)
		for k in range(len(lii)):
			li[lii[k]] = '1'
	print(''.join(li))


T = int(input())
while T > 0:
	T -= 1
	(n, m) = map(int, input().split())
	S = input()
	s = []
	for c in S:
		if c == '1':
			s.append(1)
		else:
			s.append(0)
	ok = False
	i = 0
	while i < n:
		if s[i] == 1:
			if not ok:
				j = i - 1
				cnt = m
				while cnt > 0 and j >= 0:
					s[j] = 1
					cnt -= 1
					j -= 1
				ok = True
			if i == n - 1:
				break
			if s[i + 1] == 0:
				j = i + 1
				cnt = 0
				while j < n and s[j] != 1:
					cnt += 1
					j += 1
				if j == n:
					j = i + 1
					cnt = m
					while cnt > 0 and j < n:
						s[j] = 1
						cnt -= 1
						j += 1
				else:
					if cnt & 1:
						cnt -= 1
					M = min(cnt / 2, m)
					cnt = M
					k = i + 1
					while cnt > 0:
						s[k] = 1
						cnt -= 1
						k += 1
					cnt = M
					k = j - 1
					while cnt > 0:
						s[k] = 1
						cnt -= 1
						k -= 1
				i = j - 1
		i += 1
	for i in s:
		print(i, end='')
	print()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	str = input()
	l = []
	a = []
	for i in range(len(str)):
		if str[i] == '1':
			l.append(i)
	if len(l) == 0:
		print(str)
	else:
		g = min(l[0], m)
		a.append((l[0] - g, max(0, l[0] - 1)))
		for i in range(len(l) - 1):
			q = l[i + 1] - 1 - l[i]
			if q >= 2 * m:
				a.append((l[i] + 1, l[i] + m))
				a.append((l[i + 1] - m, l[i + 1] - 1))
			elif q > 1 and q < 2 * m:
				if q % 2 == 0:
					a.append((l[i] + 1, l[i + 1] - 1))
				else:
					a.append((l[i] + 1, l[i] + q // 2))
					a.append((l[i + 1] - q // 2, l[i + 1] - 1))
		g = min(n - 1 - l[-1], m)
		a.append((min(l[-1] + 1, n - 1), l[-1] + g))
		for i in range(len(a)):
			r = a[i][0]
			t = a[i][-1]
			str = str[:r] + '1' * (t - r + 1) + str[t + 1:n]
		print(str)


t = int(input())
for i in range(0, t):
	(n, m) = list(map(int, input().split()))
	s = input()
	l = []
	for j in range(0, n):
		if s[j] == '1':
			l.append(1)
		else:
			l.append(0)
	f = 0
	c = 0
	while f == 0 and c < m:
		f = 1
		l1 = []
		for j in range(0, n):
			if j == 0 and l[j] == 0 and (l[j + 1] == 1):
				l1.append(j)
				f = 0
			elif j == n - 1 and l[j] == 0 and (l[j - 1] == 1):
				l1.append(j)
				f = 0
			elif j > 0 and j < n - 1:
				if l[j] == 0 and (l[j - 1] == 1 and l[j + 1] == 0 or (l[j - 1] == 0 and l[j + 1] == 1)):
					l1.append(j)
					f = 0
		c += 1
		if f == 1:
			break
		for j in l1:
			l[j] = 1
	for j in l:
		print(j, end='')
	print()


import sys
import math
import heapq
from collections import defaultdict as dd
from itertools import permutations as pp
from itertools import combinations as cc
from sys import stdin
from functools import cmp_to_key
input = stdin.readline
m = 10 ** 9 + 7
sys.setrecursionlimit(10 ** 5)
T = int(input())
for _ in range(T):
	(n, m) = map(int, input().split())
	s = input().strip()
	l = list(s)
	c = l.count('1')
	while m:
		x = 0
		i = 1
		idx = []
		while i < n - 1:
			if l[i] == '0':
				if l[i - 1] == '1' and l[i + 1] == '0' or (l[i - 1] == '0' and l[i + 1] == '1'):
					x += 1
					idx.append(i)
					i += 1
				else:
					i += 1
			else:
				i += 1
		if l[0] == '0' and l[1] == '1':
			x += 1
			idx.append(0)
		if l[-1] == '0' and l[-2] == '1':
			x += 1
			idx.append(n - 1)
		for j in idx:
			l[j] = '1'
		if x == 0:
			break
		m -= 1
	print(''.join(l))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = input()
	for _ in range(m):
		last = s
		s = ''.join(['1' if c == '1' or (i != 0 and s[i - 1] == '1') ^ (i + 1 != n and s[i + 1] == '1') else '0' for (i, c) in enumerate(s)])
		if last == s:
			break
	print(s)


t = int(input())
for test in range(t):
	(n, m) = map(int, input().split())
	s = input()
	ind = []
	for i in range(n):
		if s[i] == '1':
			ind.append(i)
	arr = [0 for x in range(n)]
	for i in ind:
		arr[i] = 1
	lr = [[-1, -1] for x in range(n)]
	prev = -1
	for i in range(n):
		if arr[i] == 0:
			lr[i][0] = prev
		else:
			prev = i
	prev = -1
	for i in range(n - 1, -1, -1):
		if arr[i] == 0:
			lr[i][1] = prev
		else:
			prev = i
	for i in range(n):
		if arr[i] == 0:
			if lr[i][0] == -1 and lr[i][1] == -1:
				arr[i] = 0
				continue
			elif lr[i][0] == -1:
				if lr[i][1] - i <= m:
					arr[i] = 1
			elif lr[i][1] == -1:
				if i - lr[i][0] <= m:
					arr[i] = 1
			elif i - lr[i][0] != lr[i][1] - i:
				mindi = min(i - lr[i][0], lr[i][1] - i)
				if mindi <= m:
					arr[i] = 1
	for i in arr:
		print(str(i), end='')
	print()


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(input())
	dic = {}
	for i in range(n):
		arr[i] = int(arr[i])
	t = []
	count = 0
	j = 0
	for i in range(n):
		if arr[i] == 0:
			count += 1
		else:
			dic[i] = 1
			if count == 0:
				j = i + 1
				continue
			t.append([count, j, i - 1])
			j = i + 1
			count = 0
	if count > 0:
		t.append([count, j, n - 1])
	re = [0] * n
	for i in dic:
		re[i] = 1
	for i in range(len(t)):
		if t[i][1] == 0 and t[i][1 + 1] == n - 1:
			break
		if t[i][1] == 0:
			for j in range(min(k, t[i][0])):
				re[t[i][1 + 1] - j] = 1
		elif t[i][1 + 1] == n - 1:
			for j in range(min(k, t[i][0])):
				re[t[i][1] + j] = 1
		else:
			for j in range(min(k, t[i][0] // 2)):
				re[t[i][1] + j] = 1
				re[t[i][1 + 1] - j] = 1
	for i in re:
		print(i, end='')
	print()


for iii in range(int(input())):
	(n, m) = map(int, input().split())
	q = input()
	q = list(q)
	if q.count('1') == 0:
		print(''.join(q))
		continue
	ind = 0
	for i in range(len(q)):
		if q[i] == '1':
			x = i - 1
			ind = i
			for ii in range(x, max(-1, x - m), -1):
				q[ii] = '1'
			break
	z = 0
	he = 0
	while True:
		count = 0
		for i in range(ind + 1, len(q)):
			if q[i] == '1':
				z = i
				break
			count += 1
		else:
			break
		for i in range(ind + 1, min(ind + 1 + m, ind + 1 + count // 2)):
			q[i] = '1'
		for i in range(max(z - count // 2, z - m), z):
			q[i] = '1'
		ind = z
		he += 1
	indi = -1
	for i in range(len(q) - 1, -1, -1):
		if q[i] == '1':
			indi = i
			break
	if indi != -1:
		for i in range(indi + 1, min(indi + 1 + m, len(q))):
			q[i] = '1'
	print(''.join(q))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(input())
	if '1' in a:
		z = 0
		b = ''
		for x in a:
			if x == '1':
				if z:
					if b:
						d = min(z // 2, m)
						b += '1' * d + '0' * (z - d * 2) + '1' * d
					else:
						d = min(z, m)
						b += '0' * (z - d) + '1' * d
				b += '1'
				z = 0
			else:
				z += 1
		d = min(z, m)
		b += '1' * d + '0' * (z - d)
		print(b)
	else:
		print(''.join(a))


from collections import Counter
import math
from bisect import bisect
import sys
MOD = 1000000007
MAX = sys.maxsize
MIN = -sys.maxsize

class get:

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

	def str():
		return input().split()

	def float():
		return list(map(float, input().split()))

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

def sqrt(x):
	return int(math.sqrt(x)) + 1

def gcd(*args):
	result = args[0]
	for item in args:
		result = math.gcd(result, item)
	return result

def LCM(a, b):
	return a * b // math.gcd(a, b)

def solve():
	(n, m) = get.map()
	s = list(input())
	if s == ['0'] * n:
		print(''.join(s))
	else:
		mylist = []
		for i in range(n):
			if s[i] == '1':
				mylist.append(i)
		for i in range(n):
			if s[i] == '0':
				a = bisect(mylist, i)
				if a == 0:
					required = mylist[0] - i
					if required <= m:
						s[i] = '1'
				elif a == len(mylist):
					required = i - mylist[-1]
					if required <= m:
						s[i] = '1'
				else:
					left = i - mylist[a - 1]
					right = mylist[a] - i
					if left != right and min(left, right) <= m:
						s[i] = '1'
		print(''.join(s))
for _ in range(int(input())):
	solve()


from sys import stdin, stdout
input = stdin.readline

def output(answer):
	stdout.write('{}\n'.format(answer))
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = input()
	arr = []
	for i in s[:-1]:
		arr.append(int(i))
	answer = [0 for i in range(n)]
	for i in range(n):
		if arr[i] == 0:
			(left, right) = (1e+18, 1e+18)
			for j in range(i - 1, -1, -1):
				if arr[j] == 1:
					left = j
					break
			for j in range(i + 1, n):
				if arr[j] == 1:
					right = j
					break
			(d1, d2) = (i - left, right - i)
			if left == 1e+18:
				d1 = 1e+18
			if right == 1e+18:
				d2 = 1e+18
			if d1 != d2:
				if min(d1, d2) <= m:
					answer[i] = 1
		else:
			answer[i] = 1
	ans = []
	for i in answer:
		ans.append(str(i))
	ans = ''.join(ans)
	output(ans)


import sys
input = sys.stdin.readline
t = int(input())
for i in range(t):
	ans = 0
	(n, m) = map(int, input().split())
	a = input().strip()
	a = list(a)
	flag = True
	flag2 = True
	j = 0
	while flag:
		temp = a.copy()
		for i in range(n):
			if a[i] == '0':
				if i == 0:
					if temp[1] == '1':
						a[i] = '1'
						flag = False
				elif i == n - 1:
					if temp[n - 2] == '1':
						a[i] = '1'
						flag = False
				elif int(temp[i - 1]) + int(temp[i + 1]) == 1:
					a[i] = '1'
					flag = False
		j += 1
		if j == m:
			print(''.join(a))
			flag2 = False
		flag = not flag
	if flag2:
		print(''.join(a))


from os import path
import sys, time
from math import ceil, floor, gcd, log, log2, factorial, sqrt
from collections import defaultdict, Counter, OrderedDict, deque
from itertools import combinations, accumulate
from bisect import *
from functools import reduce
from operator import mul
star = lambda x: print(' '.join(map(str, x)))
grid = lambda r: [lint() for i in range(r)]
INF = float('inf')
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
import sys
from sys import stdin, stdout
from collections import *
from math import gcd, floor, ceil

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

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

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

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

def solve():
	(n, m) = invr()
	a = list(input())
	li = a.copy()
	t = min(n, m)
	for i in range(t):
		for j in range(n):
			if j == 0:
				if a[j + 1] == '1':
					li[j] = '1'
			elif j == n - 1:
				if a[j - 1] == '1':
					li[j] = '1'
			elif a[j - 1] == '1' and a[j + 1] == '0' or (a[j - 1] == '0' and a[j + 1] == '1'):
				li[j] = '1'
		a = li.copy()
	print(''.join(li))
t = 1
t = inp()
for _ in range(t):
	solve()


from collections import Counter, deque, defaultdict
from itertools import accumulate, product, groupby
import operator
import math
from functools import reduce

def solve():
	(n, m) = map(int, input().split())
	s = input()
	s = '0' + s + '0'
	for i in range(min(m, n)):
		while '101' in s:
			s = s.replace('101', '121')
		s = s.replace('10', '11')
		s = s.replace('01', '11')
	while '121' in s:
		s = s.replace('121', '101')
	return s[1:n + 1]
for _ in range(int(input())):
	print(solve())


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	arr = list(input())
	while m > 0:
		changes_for_itr = 0
		ind_to_change = []
		if arr[0] == '0' and arr[1] == '1':
			arr[0] = '1'
			changes_for_itr += 1
		if arr[n - 1] == '0' and arr[n - 2] == '1':
			arr[n - 1] = '1'
			changes_for_itr += 1
		for i in range(1, n - 1):
			if arr[i] == '0':
				if arr[i - 1] == '1' and arr[i + 1] == '0' or (arr[i - 1] == '0' and arr[i + 1] == '1'):
					ind_to_change.append(i)
					changes_for_itr += 1
		for ind in ind_to_change:
			arr[ind] = '1'
		ind_to_change.clear()
		if changes_for_itr == 0:
			break
		m -= 1
	print(''.join(arr))


for t in range(int(input())):
	l = list(map(int, input().split()))
	n = l[0]
	m = l[1]
	a = list(input())
	ar = []
	for i in a:
		ar.append(int(i))
	p1 = 0
	p2 = 0
	np1 = 0
	np2 = 0
	while p1 < n:
		if ar[p1] == 1:
			p1 += 1
			continue
		p2 = p1
		while p2 < n - 1 and ar[p2 + 1] != 1:
			p2 += 1
		if p1 == 0 and p2 == n - 1:
			break
		if p1 == 0:
			np2 = p2
			for i in range(m, 0, -1):
				if np2 >= 0:
					ar[np2] = 1
					np2 -= 1
				else:
					break
		elif p2 == n - 1:
			np1 = p1
			for i in range(m, 0, -1):
				if np1 < n:
					ar[np1] = 1
					np1 += 1
				else:
					break
		else:
			np2 = p2
			np1 = p1
			for i in range(m, 0, -1):
				if np2 >= 0 and np1 < n and (np1 < np2):
					ar[np1] = 1
					ar[np2] = 1
					np1 += 1
					np2 -= 1
				else:
					break
		p1 = p2 + 1
	for i in ar:
		print(i, end='')
	print()


t = int(input())
import math

def binarySearch(arr, l, r, x):
	if r >= l:
		mid = l + (r - l) // 2
		if arr[mid] == x:
			return mid
		elif arr[mid] > x:
			return binarySearch(arr, l, mid - 1, x)
		else:
			return binarySearch(arr, mid + 1, r, x)
	else:
		return -1
for _ in range(t):
	(n, m) = map(int, input().split())
	s = input()
	l = list(s)
	i = 0
	while i < n and l[i] == '0':
		i += 1
	k = -1
	while k >= -n and l[k] == '0':
		k -= 1
	if i < n:
		for j in range(min(i, m)):
			l[i - j - 1] = '1'
		for j in range(min(-1 - k, m)):
			l[k + j + 1] = '1'
		while i < n + k:
			if l[i] == '0':
				low = i
				while i < n + k and l[i] == '0':
					i += 1
				for j in range(min(m, (i - low) // 2)):
					l[low + j] = '1'
					l[i - j - 1] = '1'
			else:
				i += 1
	for i in range(n):
		print(l[i], end='')
	print('\n')


from sys import stdin, stdout
intn = lambda : int(stdin.readline())
strs = lambda : stdin.readline()[:-1]
lstr = lambda : list(stdin.readline()[:-1])
mint = lambda : map(int, stdin.readline().split())
lint = lambda : list(map(int, stdin.readline().split()))
out = lambda x: stdout.write(str(x) + '\n')
out_ = lambda x: stdout.write(str(x) + ' ')

def main():
	for _ in range(intn()):
		(n, m) = mint()
		s = lstr()
		if s == ['0'] * n:
			print(*s, sep='')
			continue
		x = s.index('1')
		s[max(0, x - m):x] = ['1'] * min(m, x)
		i = x + 1
		while i < n:
			if s[i] == '1':
				q = min((i - x - 1) // 2, m)
				s[x + 1:x + 1 + q] = ['1'] * q
				s[i - q:i] = ['1'] * q
				x = i
			i += 1
		s[x + 1:min(n, x + m + 1)] = ['1'] * min(m, n - x - 1)
		print(''.join(s))
main()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = input()
	s = '0' + s
	l = [-10000000000.0] * (n + 2)
	r = [10000000000.0] * (n + 2)
	for i in range(1, n + 1):
		l[i] = l[i - 1]
		if s[i] == '1':
			l[i] = i
	for i in range(n, 0, -1):
		r[i] = r[i + 1]
		if s[i] == '1':
			r[i] = i
	res = ''
	for i in range(1, n + 1):
		if s[i] == '1':
			res += '1'
		elif s[i] == '0' and (l[i] + 1 < i or r[i] - 1 > i) and (l[i] + m >= i or r[i] - m <= i) and (l[i] + r[i] != 2 * i):
			res += '1'
		else:
			res += '0'
	print(res)


t = int(input())
for _ in range(t):
	(n, m) = (int(i) for i in input().split())
	s = [int(i) for i in input()]
	(le, ri, res) = (0, 0, s)
	while ri < n:
		while ri < n - 1 and res[ri] == 0:
			ri += 1
		(lo, hi, rem) = (le, ri, min(m, n))
		while rem > 0 and (hi - lo > 2 or res[lo] == 0 or res[hi] == 0):
			if res[lo] == 1:
				res[lo + 1] = 1
				lo += 1
			if res[hi] == 1:
				res[hi - 1] = 1
				hi -= 1
			rem -= 1
		(le, ri) = (ri, ri + 1)
	res = ''.join((str(i) for i in res))
	print(res)


from collections import Counter, defaultdict, deque
import math
import sys
input = sys.stdin.readline

def solve():
	(a, b) = [int(x) for x in input().split()]
	s = [int(x) for x in input().strip()]
	rec = [10 ** 10] * a
	cur = 0
	for i in range(a):
		if s[i] == 1:
			rec[i] = 0
			cur = 1
		elif cur > 0:
			rec[i] = cur
			cur += 1
	cur = 0
	for i in range(a - 1, -1, -1):
		if s[i] == 1:
			cur = 1
		elif cur > 0:
			if rec[i] != cur:
				rec[i] = min(rec[i], cur)
			else:
				rec[i] = 10 ** 10
			cur += 1
	for i in range(a):
		print(1 if rec[i] != 10 ** 10 and rec[i] <= b else 0, end='')
	print()
tt = int(input())
for test in range(tt):
	solve()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = list(input())
	ans = [0 for i in range(len(s))]
	max_ = 1000000001
	i = len(s) - 1
	while i >= 0:
		flag = 1
		if s[i] == '1':
			ans[i] = 0
			flag = 0
		elif i + 1 < len(s):
			ans[i] = ans[i + 1] + 1
			flag = 0
		if flag == 1:
			ans[i] = max_
		i -= 1
	ans1 = [0 for i in range(len(s))]
	i = 0
	while i < len(s):
		flag = 1
		if s[i] == '1':
			ans1[i] = 0
			flag = 0
		elif i - 1 >= 0:
			ans1[i] = 1 + ans1[i - 1]
			flag = 0
		if flag == 1:
			ans1[i] = max_
		i += 1
	w = ''
	for i in range(len(s)):
		if ans[i] == ans1[i] and ans[i] != 0:
			w += '0'
		elif min(ans[i], ans1[i]) <= m:
			w += '1'
		else:
			w += '0'
	print(w)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = input()
	s = list(s)
	for _ in range(m):
		l = []
		for x in range(n):
			if s[x] == '0':
				if x == 0:
					if s[x + 1] == '1':
						l.append(x)
				elif x == len(s) - 1:
					if s[x - 1] == '1':
						l.append(x)
				elif s[x + 1] == '0' and s[x - 1] == '0':
					continue
				elif s[x + 1] == '0' or s[x - 1] == '0':
					l.append(x)
		if l == []:
			break
		else:
			for x in l:
				s[x] = '1'
	print(''.join(s))


import bisect

def solve():
	(n, m) = map(int, input().split())
	s = input()
	inf = float('inf')
	I = [-inf] + [i for i in range(n) if s[i] == '1'] + [inf]
	ans = ['0'] * n
	for i in range(n):
		k = bisect.bisect_left(I, i)
		d = min(I[k] - i, i - I[k - 1])
		if I[k] - i == i - I[k - 1]:
			continue
		if d <= m:
			ans[i] = '1'
	print(''.join(ans))
for nt in range(int(input())):
	solve()


def sol(A, n):
	if sum([int(a) for a in A]) == 0:
		return A
	A = A.split('1')
	for i in range(1, len(A) - 1):
		l = len(A[i])
		if l > 0:
			A[i] = '1' * min(n, l // 2) + '0' * (l - 2 * min(n, l // 2)) + '1' * min(n, l // 2)
	ans = ''
	for i in range(len(A)):
		if A[i] != '':
			ans += A[i]
		if i < len(A) - 1:
			ans += '1'
	for i in range(len(ans)):
		if ans[i] == '1':
			break
	ans = '0' * (i - min(n, i)) + '1' * min(n, i) + ans[i:]
	for i in range(len(ans) - 1, -1, -1):
		if ans[i] == '1':
			break
	l = len(ans) - i - 1
	ans = ans[:i + 1] + '1' * min(n, l) + '0' * (l - min(n, l))
	return ans
x = int(input())
for _ in range(x):
	y = list(map(int, input().split()))
	A = input()
	print(sol(A, y[1]))


def get_1_indexes(s, len_arr):
	s_1 = [i for i in range(len_arr) if s[i] == '1']
	return s_1

def solve(s, num_iter, len_arr):
	s1 = get_1_indexes(s, len_arr)
	s_orig = [x for x in s]
	len_s1 = len(s1)
	if len_s1 == 0:
		return s
	s = list(s)
	curr = max(0, s1[0] - num_iter)
	next = s1[0]
	for i in range(len_s1):
		for j in range(curr, next):
			if s[j] == '0' and (j - curr != next - j or s_orig[curr] == '0'):
				if j - curr <= num_iter or next - j <= num_iter:
					s[j] = '1'
		curr = s1[i]
		if i + 1 == len_s1:
			next = min(s1[i] + num_iter + 1, len_arr)
		else:
			next = s1[i + 1]
	for j in range(curr, next):
		s[j] = '1'
	return ''.join(s)
num_t = int(input())
sols = []
for x in range(num_t):
	(len_arr, num_iter) = map(int, input().split())
	s = input()
	solve(s, num_iter, len_arr)
	sols.append(solve(s, num_iter, len_arr))
print(*sols, sep='\n')


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	s = input()
	ones = []
	arr = [-1] * len(s)
	for j in range(len(s)):
		if s[j] == '1':
			ones += [j]
	if len(ones) == 1:
		for p in range(ones[0] + 1):
			arr[p] = ones[0] - p
		for q in range(1, n - ones[0]):
			arr[ones[0] + q] = q
	else:
		for e in range(len(ones)):
			if e == 0:
				for p in range(ones[0] + 1):
					arr[p] = ones[0] - p
				st = ones[e]
				en = ones[e + 1]
				arr[ones[e]] = 0
				arr[ones[e + 1]] = 0
				if en - st > 1:
					mid = (en - st - 1) // 2
					for ele in range(mid + 1):
						arr[st + ele] = ele
						arr[en - ele] = ele
			elif e == len(ones) - 1:
				for q in range(n - ones[e]):
					arr[ones[e] + q] = q
			else:
				st = ones[e]
				en = ones[e + 1]
				arr[ones[e]] = 0
				arr[ones[e + 1]] = 0
				if en - st > 1:
					mid = (en - st - 1) // 2
					for ele in range(mid + 1):
						arr[st + ele] = ele
						arr[en - ele] = ele
	finals = ''
	for r in range(len(arr)):
		if arr[r] <= m and arr[r] != -1:
			finals += '1'
		else:
			finals += '0'
	print(finals)


import sys
from os import path
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, list(input())))
	for j in range(min(m, n)):
		for i in range(n):
			prev = 0 if i - 1 < 0 else a[i - 1]
			if prev == 2:
				prev = 0
			next = 0 if i + 1 >= n else a[i + 1]
			if next == 2:
				next = 0
			if a[i] == 0 and next + prev == 1:
				a[i] = 2
		for i in range(n):
			if a[i] == 2:
				a[i] = 1
	print(''.join(map(str, a)))


for _ in range(int(input())):
	(a, b) = [int(x) for x in input().split()]
	c = input().split('1')
	if len(c) == 1:
		print(*c)
	else:
		for j in range(len(c)):
			t = c[j]
			if j == 0 and len(c[j]) > b:
				c[j] = '0' * (len(t) - b) + '1' * b
			elif j == len(c) - 1 and len(c[j]) > b:
				c[j] = '1' * b + '0' * (len(t) - b)
			elif (j == 0 or j == len(c) - 1) or (len(t) % 2 == 0 and len(t) <= 2 * b):
				c[j] = '1' * len(t)
			elif len(t) % 2 == 1 and len(t) < 2 * b:
				c[j] = '1' * (len(t) // 2) + '0' + '1' * (len(t) // 2)
			else:
				c[j] = '1' * b + '0' * (len(t) - 2 * b) + '1' * b
		print('1'.join(c))


r = str.replace
for _ in [0] * int(input()):
	m = min(map(int, input().split()))
	s = f'0{input()}0'
	while m:
		m -= 1
		s = r(r(r(r(r(s, '100', '1*0'), '001', '0*1'), '*01', '111'), '10*', '111'), '*', '1')
	print(s[1:-1])


from sys import stdin
for _ in range(int(stdin.readline())):
	(n, m) = map(int, stdin.readline().split())
	s = list(input())
	l = []
	j = 0
	for i in s:
		if i == '1':
			l.append(j)
		j += 1
	if len(l) > 0:
		a = l[0]
	for i in l:
		y = a + 1
		z = i - 1
		t = 1
		while t <= m and y < z:
			s[y] = '1'
			s[z] = '1'
			y += 1
			z -= 1
			t += 1
		a = i
	if len(l) != 0:
		for i in range(l[0], max(0, l[0] - m) - 1, -1):
			s[i] = '1'
		for i in range(l[-1], min(n, l[-1] + m + 1)):
			s[i] = '1'
	print(''.join(s))


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	s = list(input())
	b = 0
	while b < n:
		while b < n and s[b] == '1':
			b += 1
		e = b
		while e + 1 < n and s[e + 1] == '0':
			e += 1
		if b == 0 and e == n - 1:
			break
		elif b == 0:
			for i in range(e, max(b - 1, e - m), -1):
				s[i] = '1'
		elif e == n - 1:
			for i in range(b, min(b + m, e + 1)):
				s[i] = '1'
		elif b == e:
			b += 1
			continue
		else:
			(i, j) = (b, e)
			it = 0
			while i < j and it < m:
				(s[i], s[j]) = ('1', '1')
				i += 1
				j -= 1
				it += 1
		b = e + 1
	print(''.join(s))


import os
import sys
from io import BytesIO, IOBase
ONLINE_JUDGE = 1

def main():
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		a = list(map(int, input()))
		a_ = a[:]
		for _ in range(min(n, m)):
			if a[1] == 1:
				a_[0] = 1
			if a[-2] == 1:
				a_[-1] = 1
			for i in range(1, n - 1):
				if a[i] == 0:
					if a[i - 1] == 0 and a[i + 1] == 1:
						a_[i] = 1
					elif a[i - 1] == 1 and a[i + 1] == 0:
						a_[i] = 1
			a = a_[:]
		print(*a, sep='')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')
if not ONLINE_JUDGE:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
main()


def solve(n, m, A):
	flags = [[-10 ** 10, 10 ** 10] for _ in range(n)]
	prev = -10 ** 10
	for (i, a) in enumerate(A):
		if a == '1':
			prev = i
		flags[i][0] = prev
	prev = 10 ** 10
	for (i, a) in enumerate(A[::-1]):
		if a == '1':
			prev = n - i - 1
		flags[n - i - 1][1] = prev
	counts = []
	for (i, (prev, nex)) in enumerate(flags):
		if i == prev:
			counts.append(0)
		elif i - prev == nex - i:
			counts.append(10 ** 10)
		else:
			counts.append(min(i - prev, nex - i))
	ans = ''
	for cnt in counts:
		if cnt <= m:
			ans += '1'
		else:
			ans += '0'
	return ans

def main():
	ans = []
	t = int(input())
	for _ in range(t):
		(n, m) = map(int, input().split(' '))
		A = input()
		ans.append(solve(n, m, A))
	for a in ans:
		print(a)
main()


import bisect
import copy
import decimal
import fractions
import heapq
import itertools
import math
import random
import sys
from collections import Counter, deque, defaultdict
from functools import lru_cache, reduce
from heapq import heappush, heappop, heapify, _heappop_max, _heapify_max

def _heappush_max(heap, item):
	heap.append(item)
	heapq._siftdown_max(heap, 0, len(heap) - 1)
from math import gcd as Gcd
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
t = int(readline())
for _ in range(t):
	(n, m) = map(int, readline().split())
	cell = readline().rstrip()
	bound = []
	l = 0
	while l != n:
		if cell[l] == '0':
			l += 1
		else:
			r = l
			while r != n and cell[r] == '1':
				r += 1
			bound.append([l, r])
			l = r
	L = len(bound)
	if bound:
		bound[0][0] = max(0, bound[0][0] - m)
		bound[L - 1][1] = min(n, bound[L - 1][1] + m)
	for i in range(L - 1):
		if bound[i][1] + m < bound[i + 1][0] - m:
			bound[i][1] += m
			bound[i + 1][0] -= m
		else:
			(a, b) = (bound[i][1], bound[i + 1][0])
			bound[i][1] = (a + b) // 2
			bound[i + 1][0] = a + b - bound[i][1]
	ans_lst = ['0'] * n
	for (l, r) in bound:
		for i in range(l, r):
			ans_lst[i] = '1'
	print(*ans_lst, sep='')


import io
import os
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappush, heappop, heapify
from math import gcd, inf

def solve(N, M, A):
	for _ in range(M):
		B = [0] * N
		for i in range(N):
			if A[i]:
				B[i] = 1
			else:
				nbr = (0 <= i - 1 and A[i - 1]) + (i + 1 < N and A[i + 1])
				if nbr == 1:
					B[i] = 1
		if A == B:
			break
		A = B
	return ''.join(map(str, A))
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
TC = int(input())
for tc in range(1, TC + 1):
	(N, M) = [int(x) for x in input().split()]
	A = [int(x) for x in input().decode().rstrip()]
	ans = solve(N, M, A)
	print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
from bisect import bisect_left, bisect_right

class Result:

	def __init__(self, index, value):
		self.index = index
		self.value = value

class BinarySearch:

	def __init__(self):
		pass

	@staticmethod
	def greater_than(num: int, func, size: int=1):
		if isinstance(func, list):
			index = bisect_right(func, num)
			if index == len(func):
				return Result(None, None)
			else:
				return Result(index, func[index])
		else:
			(alpha, omega) = (0, size - 1)
			if func(omega) <= num:
				return Result(None, None)
			while alpha < omega:
				if func(alpha) > num:
					return Result(alpha, func(alpha))
				if omega == alpha + 1:
					return Result(omega, func(omega))
				mid = (alpha + omega) // 2
				if func(mid) > num:
					omega = mid
				else:
					alpha = mid

	@staticmethod
	def less_than(num: int, func, size: int=1):
		if isinstance(func, list):
			index = bisect_left(func, num) - 1
			if index == -1:
				return Result(None, None)
			else:
				return Result(index, func[index])
		else:
			(alpha, omega) = (0, size - 1)
			if func(alpha) >= num:
				return Result(None, None)
			while alpha < omega:
				if func(omega) < num:
					return Result(omega, func(omega))
				if omega == alpha + 1:
					return Result(alpha, func(alpha))
				mid = (alpha + omega) // 2
				if func(mid) < num:
					alpha = mid
				else:
					omega = mid
bs = BinarySearch()
for _ in range(int(input()) if True else 1):
	(n, m) = map(int, input().split())
	s = input()
	s = [k for k in s]
	for i in range(min(m, n + 10)):
		s2 = list(s)
		f = False
		for j in range(n):
			if j == 0 and s[j] == '0' and (s[j + 1] == '1') or (j == n - 1 and s[j] == '0' and (s[j - 1] == '1')):
				s2[j] = '1'
				f = True
			if j == 0 or j == n - 1:
				continue
			if s[j] == s[j - 1] == '0' and s[j + 1] == '1' or (s[j] == s[j + 1] == '0' and s[j - 1] == '1'):
				s2[j] = '1'
				f = True
		s = list(s2)
		if not f:
			break
	print(*s, sep='')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = '0' + input() + '0'
	for i in range(min(m, n)):
		s = s.replace('100', '1*0').replace('001', '0*1').replace('*01', '111').replace('10*', '111').replace('*', '1')
	print(s[1:-1])


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	s = input()
	o = []
	for i in range(len(s)):
		if s[i] == '1':
			o.append(i)
	if len(o) == 0:
		print(s)
		continue
	r = 0
	ans = ''
	for i in range(n):
		if s[i] == '1':
			r += 1
			ans += '1'
		elif r == 0:
			if abs(i - o[r]) <= m:
				ans += '1'
			else:
				ans += '0'
		elif r == len(o):
			if abs(i - o[r - 1]) <= m:
				ans += '1'
			else:
				ans += '0'
		elif (abs(i - o[r]) <= m or abs(i - o[r - 1]) <= m) and abs(i - o[r]) != abs(i - o[r - 1]):
			ans += '1'
		else:
			ans += '0'
	print(ans)


import sys, os.path, math
from collections import defaultdict, deque
if os.path.exists('amz42.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
for _ in range(int(input().strip(' '))):
	(n, k) = [int(x) for x in input().strip(' ').split(' ')]
	s = [int(x) for x in input().strip(' ')]
	if 1 not in s:
		print(*s, sep='')
		continue
	f = s.index(1)
	moves = k
	i = f - 1
	while moves > 0 and i >= 0:
		s[i] = 1
		i -= 1
		moves -= 1
	l = n - s[::-1].index(1) - 1
	moves = k
	i = l + 1
	while moves > 0 and i < n:
		s[i] = 1
		i += 1
		moves -= 1
	i = f
	while i < l:
		while i < l and s[i] == 1:
			i += 1
		j = i
		while j < l and s[j] == 0:
			j += 1
		(x, y) = (i, j - 1)
		moves = k
		while x < y and moves > 0:
			s[x] = 1
			s[y] = 1
			x += 1
			y -= 1
			moves -= 1
		i = j
	print(*s, sep='')


import sys
input = sys.stdin.readline

def solve():
	(n, m) = map(int, input().split())
	s = list(map(int, input().strip()))
	p = []
	for i in range(n):
		if s[i] == 0 and (i > 0 and s[i - 1] == 1) + (i + 1 < n and s[i + 1] == 1) == 1:
			p.append(i)
	for j in range(m):
		for i in p:
			s[i] = 1
		q = []
		for v in p:
			for i in (v - 1, v + 1):
				if i >= 0 and i < n and (s[i] == 0) and ((i > 0 and s[i - 1] == 1) + (i + 1 < n and s[i + 1] == 1) == 1):
					q.append(i)
		if len(q) == 0:
			break
		p = q
	print(''.join(map(str, s)))
for i in range(int(input())):
	solve()


t = int(input())

def to_alive(i, L):
	return L[i - 1] == '0' and L[i + 1] == '1' or (L[i - 1] == '1' and L[i + 1] == '0')
for _ in range(t):
	(N, M) = map(int, input().split())
	S = input()
	L = []
	for char in S:
		L.append(char)
	count = 0
	for i in range(M):
		temp = L[:]
		if L[1] == '1':
			temp[1] = '1'
			temp[0] = '1'
		if L[N - 2] == '1':
			temp[N - 2] = '1'
			temp[-1] = '1'
		for j in range(1, N - 1):
			if L[1] == '1':
				temp[1] = '1'
				temp[0] = '1'
			if L[N - 2] == '1':
				temp[N - 2] = '1'
				temp[-1] = '1'
			if to_alive(j, L):
				temp[j] = '1'
		if L == temp:
			count += 1
		if count > 10:
			break
		L = temp[:]
	print(''.join(L))


t = int(input())
while t:
	t -= 1
	(n, m) = map(int, input().split())
	s = input()
	l = list(s)
	c = l.copy()
	for _ in range(0, m):
		check = 0
		for i in range(0, n):
			f1 = 0
			f2 = 0
			if l[i] != '1':
				if i - 1 >= 0 and l[i - 1] == '1':
					f1 = 1
				if i + 1 < n and l[i + 1] == '1':
					f2 = 1
				if f1 == 1 and f2 == 0 or (f1 == 0 and f2 == 1):
					c[i] = '1'
		if c == l:
			break
		l = c.copy()
	ans = ''.join(l)
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = input()
	cnt = 0
	ones = []
	for i in range(n):
		if s[i] == '1':
			ones.append(i)
	if len(ones) == 0:
		print(s)
	else:
		ans = [0] * n
		for i in ones:
			ans[i] = 1
		j = ones[0] - 1
		ones = [-ones[0] - 1] + ones + [n * 2 - ones[-1] - 1]
		for i in range(1, len(ones) - 1):
			idx = ones[i]
			j = idx - 1
			d1 = idx - ones[i - 1] - 1
			while idx - j <= min(d1 // 2, m):
				ans[j] = 1
				j -= 1
			j = idx + 1
			d2 = ones[i + 1] - idx - 1
			while j - idx <= min(d2 // 2, m):
				ans[j] = 1
				j += 1
		print(*ans, sep='')


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	st = input()
	s = list(st)
	for j in range(min(m, n)):
		c = 0
		for i in range(n):
			if st[i] == '0':
				if i == 0:
					if st[1] == '1':
						s[0] = '1'
						c += 1
				elif i == n - 1:
					if st[n - 2] == '1':
						s[n - 1] = '1'
						c += 1
				elif st[i - 1] == '1' and st[i + 1] == '0' or (st[i - 1] == '0' and st[i + 1] == '1'):
					s[i] = '1'
					c += 1
		st = ''.join(s)
		if c == 0:
			break
	print(st)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(input())
	ind = []
	for i in range(n):
		if l[i] == '1':
			ind.append(i)
	i = 0
	for j in ind:
		t = m
		temp = j
		j = j - 1
		if i == 0:
			while j >= 0 and t > 0:
				l[j] = '1'
				j -= 1
				t -= 1
		else:
			while t > 0 and i < j:
				l[i] = '1'
				l[j] = '1'
				i += 1
				j -= 1
				t -= 1
		i = temp + 1
	if len(ind) > 0 and ind[-1] != n - 1:
		i = ind[-1] + 1
		while i < n and m > 0:
			l[i] = '1'
			i += 1
			m -= 1
	print(''.join(l))


def ints(separator=' '):
	return [int(x) for x in input().split(separator)]
for t in range(int(input())):
	(n, m) = ints()
	a = [int(x) for x in input()]
	left = []
	right = []
	k = -1
	for i in range(n):
		if a[i] == 1:
			k = i
		left.append(n + 1 if k == -1 else i - k)
	k = -1
	for i in range(n - 1, -1, -1):
		if a[i] == 1:
			k = i
		right.insert(0, n + 1 if k == -1 else k - i)
	for i in range(n):
		if left[i] != 0 and left[i] == right[i]:
			a[i] = 0
		else:
			a[i] = 1 if min(left[i], right[i]) <= m else 0
	print(''.join([str(x) for x in a]))


for _ in range(int(input())):
	(n, t) = map(int, input().split())
	s = input()
	for i in range(min(n, t)):
		s = s.replace('101', '121')
		s = s.replace('101', '121')
		s = s.replace('10', '11')
		s = s.replace('01', '11')
		s = s.replace('2', '0')
	print(''.join(s))


from collections import deque, defaultdict
from math import sqrt, ceil, factorial, floor, inf, gcd, log
import bisect
import sys
import copy

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

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

def input():
	return sys.stdin.readline().strip()
for _ in range(int(input())):
	(n, k) = get_ints()
	s = list(input())
	arr = ['0'] * n
	time = [0] * n
	i = -1
	while i < n - 1:
		i += 1
		if s[i] == '1':
			arr[i] = '1'
			j = i - 1
			t = 1
			while j >= max(0, i - k):
				if s[j] == '1':
					break
				if arr[j] == '1' and time[j] == t:
					arr[j] = '0'
					break
				if arr[j] == '1' and time[j] < t:
					break
				if arr[j] == '1' and time[j] > t:
					time[j] = t
				arr[j] = '1'
				time[j] = t
				t += 1
				j -= 1
			t = 1
			j = i + 1
			while j < min(i + k + 1, n):
				if s[j] == '1':
					break
				if arr[j] == '1' and time[j] == t:
					s[j] = '0'
					break
				if arr[j] == '1' and time[j] < t:
					break
				if arr[j] == '1' and time[j] > t:
					time[j] = t
				arr[j] = '1'
				time[j] = t
				t += 1
				j += 1
	print(''.join(arr))