You are given a binary string of length $n$. You have exactly $k$ moves. In one move, you must select a single bit. The state of all bits except that bit will get flipped ($0$ becomes $1$, $1$ becomes $0$). You need to output the lexicographically largest string that you can get after using all $k$ moves. Also, output the number of times you will select each bit. If there are multiple ways to do this, you may output any of them.

A binary string $a$ is lexicographically larger than a binary string $b$ of the same length, if and only if the following holds:

in the first position where $a$ and $b$ differ, the string $a$ contains a $1$, and the string $b$ contains a $0$.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 1000$)  — the number of test cases.

Each test case has two lines. The first line has two integers $n$ and $k$ ($1 \leq n \leq 2 \cdot 10^5$; $0 \leq k \leq 10^9$).

The second line has a binary string of length $n$, each character is either $0$ or $1$.

The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, output two lines.

The first line should contain the lexicographically largest string you can obtain.

The second line should contain $n$ integers $f_1, f_2, \ldots, f_n$, where $f_i$ is the number of times the $i$-th bit is selected. The sum of all the integers must be equal to $k$.


-----Examples-----

Input
6
6 3
100001
6 4
100011
6 0
000000
6 1
111001
6 11
101100
6 12
001110
Output
111110
1 0 0 2 0 0 
111110
0 1 1 1 0 1 
000000
0 0 0 0 0 0 
100110
1 0 0 0 0 0 
111111
1 2 1 3 0 4 
111110
1 1 4 2 0 4


-----Note-----

Here is the explanation for the first testcase. Each step shows how the binary string changes in a move.

Choose bit $1$: ${\underline{1}00001} \rightarrow {\underline{1}}\color{blue}{11110}$.

Choose bit $4$: ${111\underline{1}10} \rightarrow \color{blue}{000}{\underline{1}}\color{blue}{01}$.

Choose bit $4$: ${000\underline{1}01} \rightarrow \color{blue}{111}{\underline{1}}\color{blue}{10}$.

The final string is $111110$ and this is the lexicographically largest string we can get.

Source: codeforces | Difficulty: EASY
Tags: String algorithms

Bit manipulation

Constructive algorithms

Greedy algorithms


Solutions:
import sys

def solve():
	inp = sys.stdin.readline
	(n, k) = map(int, inp().split())
	s = list(inp())
	s.pop()
	r = [0] * n
	k_bak = k
	if k % 2 == 0:
		for i in range(0, n - 1):
			if s[i] == '0' and k > 0:
				s[i] = '1'
				r[i] = 1
				k -= 1
		r[-1] = k
		if (k_bak - k) % 2:
			s[-1] = str(int(s[-1]) ^ 1)
	else:
		for i in range(0, n - 1):
			if s[i] == '1' and k > 0:
				s[i] = '1'
				r[i] = 1
				k -= 1
			elif s[i] == '1':
				s[i] = '0'
			else:
				s[i] = '1'
		r[-1] = k
		if (k_bak - k) % 2:
			s[-1] = str(int(s[-1]) ^ 1)
	print(''.join(s))
	print(' '.join(map(str, r)))

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


cases = int(input())
for ca in range(cases):
	n_k = input()
	(n_, k) = n_k.split()
	n_ = int(n_)
	k = int(k)
	strr = list(input())
	strr_tmp = []
	cnt_times = [0 for _ in range(n_)]
	if k % 2 == 1:
		for (i, s) in enumerate(strr):
			if s == '1' and k:
				strr[i] = '1'
				k -= 1
				cnt_times[i] += 1
			elif s == '0':
				strr[i] = '1'
			else:
				strr[i] = '0'
	else:
		for (i, s) in enumerate(strr):
			if s == '0' and k:
				strr[i] = '1'
				k -= 1
				cnt_times[i] += 1
	if k:
		if k % 2 == 1:
			strr[n_ - 1] = '0'
		else:
			strr[n_ - 1] = '1'
	cnt_times[n_ - 1] += k
	cnt_str = [str(x) for x in cnt_times]
	print(''.join(strr))
	print(' '.join(cnt_str))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()[:-1]
	x = k
	d = [0] * n
	if k % 2:
		s1 = ''
		for i in range(n - 1):
			if x > 0:
				if s[i] == '1':
					d[i] = 1
					x -= 1
				s1 += '1'
			elif s[i] == '1':
				s1 += '0'
			else:
				s1 += '1'
		if x > 0:
			d[-1] += x
		if x % 2:
			s1 += s[-1]
		else:
			s1 += str(1 - int(s[-1]))
		print(s1)
		print(' '.join(map(str, d)))
	else:
		s1 = ''
		for i in range(n - 1):
			if x > 0:
				if s[i] == '0':
					d[i] = 1
					x -= 1
				s1 += '1'
			else:
				s1 += s[i]
		if x > 0:
			d[-1] += x
		if x % 2 == 0:
			s1 += s[-1]
		else:
			s1 += str(1 - int(s[-1]))
		print(s1)
		print(' '.join(map(str, d)))


t = int(input())

def changer(a):
	if a == '1':
		return '0'
	return '1'

def solve():
	(n, k) = map(int, input().split())
	s = input()
	res = ''
	ans = n * [0]
	z = k
	for i in range(n):
		cur = s[i]
		if (z - k) % 2 == 1:
			cur = changer(cur)
		if cur == '1':
			if k % 2 == 1:
				ans[i] = 1
				k -= 1
			res += '1'
		elif k % 2 == 0:
			if k:
				ans[i] = 1
				k -= 1
				res += '1'
			else:
				res += '0'
		else:
			res += '1'
	ans[n - 1] += k
	if k % 2 == 1:
		res = res[:n - 1] + changer(res[-1])
	print(res)
	print(' '.join(map(str, ans)))
for i in range(t):
	solve()


a = []
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = list(input())
	if k == 0:
		a.append(''.join(s))
		a.append(' '.join('0' * n))
		continue
	res = [0] * n
	cnt = 0
	idx = n
	for i in range(n):
		if cnt >= k:
			idx = i
			break
		if k & 1 and s[i] == '1' or (k & 1 == 0 and s[i] == '0'):
			res[i] += 1
			cnt += 1
	k -= cnt
	if k > 0:
		tmp = '1' * (n - 1)
		tmp += '0' if k & 1 else '1'
		res[-1] += k
	else:
		tmp = '1' * idx
		if cnt & 1:
			for j in range(idx, n):
				tmp += '1' if s[j] == '0' else '0'
		else:
			tmp += ''.join(s[idx:])
	a.append(tmp)
	a.append(' '.join((str(e) for e in res)))
for x in a:
	print(x)


T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	kc = k
	s = input()
	ans = list(s)
	flip = [0] * n
	if k % 2:
		for i in range(n):
			if k == 0:
				break
			if s[i] == '1':
				flip[i] = 1
				k -= 1
		if k > 0:
			flip[-1] += k
	else:
		for i in range(n):
			if k == 0:
				break
			if s[i] == '0':
				flip[i] = 1
				k -= 1
		if k > 0:
			flip[-1] += k
	mapp = {'1': '0', '0': '1'}
	for i in range(n):
		if (kc - flip[i]) % 2:
			ans[i] = mapp[ans[i]]
	print(''.join(ans))
	print(' '.join([str(f) for f in flip]))


from collections import defaultdict
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input().rstrip()
	s = list(map(lambda c: c == '1', s))
	flipped = set()
	if k % 2 != 0:
		s = [not x for x in s]
	for i in range(n):
		if not s[i] and k > 0:
			flipped.add(i)
			s[i] = True
			k -= 1
		if k == 0:
			break
	last_bit_add_flips = 0
	if k > 0:
		last_bit_add_flips = k
		if k % 2 != 0:
			s[-1] = not s[-1]
	result = ''.join(map(lambda x: '1' if x else '0', s))
	print(result)
	cnt_flip = list(map(lambda i: 1 if i in flipped else 0, range(n)))
	cnt_flip[-1] += last_bit_add_flips
	cnt_flip = ' '.join(map(str, cnt_flip))
	print(cnt_flip)


def solve():
	t = int(input())
	for _ in range(t):
		solve_one()

def solve_one():
	(n, k) = [int(x) for x in input().split()]
	bits = input().strip()
	if k == 0:
		print(bits)
		print(' '.join(('0' for _ in bits)))
		return
	flipped = list(bits)
	flip_num = 0
	flip_pos_num = [0 for _ in bits]
	for (i, b) in enumerate(bits):
		current_b = flip(b, flip_num)
		flipped[i] = '1'
		if should_flip_others(current_b, k - flip_num):
			flip_pos_num[i] = 1
			flip_num += 1
			if flip_num == k:
				break
	if i + 1 < len(bits):
		i += 1
		while i < len(bits):
			flipped[i] = flip(flipped[i], flip_num)
			i += 1
	else:
		flip_pos_num[-1] += k - flip_num
		flipped[-1] = flip(flipped[-1], k - flip_num)
	print(''.join(flipped))
	print(' '.join((str(x) for x in flip_pos_num)))

def flip(cur_bit: str, flip_num: int) -> str:
	if flip_num % 2 == 0:
		return cur_bit
	return '1' if cur_bit == '0' else '0'

def should_flip_others(cur_bit: str, remain_flip_num: int):
	if remain_flip_num % 2 == 0:
		return cur_bit == '0'
	else:
		return cur_bit == '1'
solve()


def main():
	t = int(input())
	for _ in range(t):
		(n, k) = map(int, input().split())
		is_odd = k & 1
		bits = [int(ele) for ele in input()]
		counts = [0] * n
		for i in range(n):
			if bits[i] == is_odd:
				bits[i] = int(k != 0)
				if k != 0:
					counts[i] += 1
					k -= 1
			else:
				bits[i] = 1
		if k != 0:
			counts[n - 1] += k
			bits[n - 1] ^= k & 1
		print(''.join([str(ele) for ele in bits]))
		print(' '.join([str(ele) for ele in counts]))
main()


cases = int(input())
for ca in range(cases):
	n_k = input()
	(n_, k) = n_k.split()
	n_ = int(n_)
	k = int(k)
	strr = list(input())
	cnt_times = [0 for _ in range(n_)]
	str_tmp = []
	first_1 = True
	first_1_index = 0
	zero_count = 0
	if k % 2 == 1:
		for (i, s) in enumerate(strr):
			if s == '0':
				str_tmp += '1'
			else:
				str_tmp += '0'
	else:
		for (i, s) in enumerate(strr):
			if s == '0':
				zero_count += 1
			str_tmp += s
	str_res = []
	for (i, s) in enumerate(str_tmp):
		if k > 0:
			if s == '0':
				str_res += '1'
				k -= 1
				cnt_times[i] += 1
			elif s == '1':
				str_res += '1'
		else:
			str_res += s
	cnt_times[n_ - 1] += k
	if k % 2 == 1:
		str_res[n_ - 1] = '0'
	cnt_str = [str(x) for x in cnt_times]
	print(''.join(str_res))
	print(' '.join(cnt_str))


cases = int(input(''))
problems = []
for test in range(0, cases):
	(n, k) = input('').split(' ')
	n = int(n)
	k = int(k)
	nums = list(input(''))
	problems.append((n, k, nums))
for (n, k, nums) in problems:
	flipped = []
	for i in range(0, n):
		flipped.append(0)
	if k % 2 != 0:
		for i in range(0, n):
			if k == 0:
				break
			if nums[i] == '1':
				k -= 1
				nums[i] = '0'
				flipped[i] += 1
		for i in range(0, n):
			if nums[i] == '0':
				nums[i] = '1'
			elif nums[i] == '1':
				nums[i] = '0'
	elif k % 2 == 0:
		for i in range(0, n):
			if k == 0:
				break
			if nums[i] == '0':
				nums[i] = '1'
				k -= 1
				flipped[i] += 1
	if k > 0:
		if k % 2 != 0:
			if nums[-1] == '0':
				nums[-1] = '1'
			else:
				nums[-1] = '0'
		flipped[-1] += k
	print(''.join(nums))
	print(' '.join([str(i) for i in flipped]))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	kc = k
	s = list(input())
	f = [0] * n
	if k % 2 == 0:
		for i in range(n):
			if k <= 0:
				break
			f[i] = 1 if s[i] == '0' else 0
			if f[i] == 1:
				k -= 1
	else:
		for i in range(n):
			if k <= 0:
				break
			f[i] = 1 if s[i] == '1' else 0
			if f[i] == 1:
				k -= 1
	lc = kc - sum(f)
	f[n - 1] += kc - sum(f)
	for i in range(n):
		if (kc - f[i]) % 2 == 1:
			s[i] = '1' if s[i] == '0' else '0'
		else:
			s[i] = '1' if s[i] == '1' else '0'
	print(''.join(s))
	print(' '.join(map(str, f)))


def solve(n, k, s):
	f = [0] * n
	if k == 0:
		return (s, f)
	if k & 1:
		idx = 0
		while idx < n:
			if s[idx] == 1:
				break
			idx += 1
		if idx == n:
			idx -= 1
		f[idx] += 1
		for i in range(n):
			if i == idx:
				continue
			s[i] = 1 - s[i]
		k -= 1
	assert k % 2 == 0
	num_zero = n - sum(s)
	idx_zero = []
	for i in range(n):
		if s[i] == 0:
			idx_zero.append(i)
	if num_zero & 1:
		idx_zero.append(n - 1)
	idx = 0
	while idx < len(idx_zero) and k > 0:
		s[idx_zero[idx]] = 1 - s[idx_zero[idx]]
		s[idx_zero[idx + 1]] = 1 - s[idx_zero[idx + 1]]
		f[idx_zero[idx]] += 1
		f[idx_zero[idx + 1]] += 1
		idx += 2
		k -= 2
	if k > 0:
		f[n - 1] += k
		k = 0
	return (s, f)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input().strip()
	s = [*map(int, list(s))]
	(s, f) = solve(n, k, s)
	s = ''.join(map(str, s))
	f = ' '.join(map(str, f))
	print(s)
	print(f)


import sys
input = sys.stdin.readline

def solve():
	(n, k) = map(int, input().split())
	ans = list(input().strip())
	d = ans[-1]
	f = [0] * n
	cnt = k
	for i in range(n):
		if not cnt:
			if k % 2:
				for j in range(i, n):
					if ans[j] == '0':
						ans[j] = '1'
					else:
						ans[j] = '0'
			print(''.join(ans))
			print(*f)
			return
		if ans[i] == '0':
			f[i] = 0 if k % 2 else 1
			cnt -= f[i]
		else:
			f[i] = 1 if k % 2 else 0
			cnt -= f[i]
		ans[i] = '1'
	f[-1] += cnt
	if cnt % 2 == 1:
		ans[-1] = '0'
	print(''.join(ans))
	print(*f)
for _ in range(int(input())):
	solve()


def solve():
	(n, k) = list(map(int, input().split(' ')))
	s = list(input())
	freq = [0] * n
	K = k
	for i in range(n):
		if k > 0:
			if s[i] == '1':
				if K & 1:
					freq[i] += 1
					k -= 1
			elif s[i] == '0':
				s[i] = '1'
				if K & 1 == 0:
					freq[i] += 1
					k -= 1
		elif K & 1:
			s[i] = '1' if s[i] == '0' else '0'
	if k > 0:
		freq[-1] += k
		if k & 1:
			s[-1] = '1' if s[-1] == '0' else '0'
	print(''.join(s))
	print(*freq)
for t in range(int(input())):
	solve()


t = int(input())
out = ''
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	string = input()
	counts = [0] * n
	count = 0
	ans = ''
	for i in range(n - 1):
		if count == k:
			if k % 2 == 0:
				ans += string[i:-1]
			else:
				for x in string[i:-1]:
					ans += str(1 - int(x))
			break
		ans += '1'
		if k % 2 == int(string[i]):
			count += 1
			counts[i] = 1
	counts[-1] += k - count
	if (counts[-1] + int(string[-1])) % 2 == k % 2:
		ans += '0'
	else:
		ans += '1'
	out += ans + '\n'
	for x in counts:
		out += str(x) + ' '
	out += '\n'
print(out)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	str = input()
	ans = ''
	indexes = [0] * n
	ost = k % 2
	if ost == 0:
		for i in range(n):
			if k == 0:
				ans += str[i:]
				break
			if str[i] == '1':
				ans += '1'
			else:
				k -= 1
				ans += '1'
				indexes[i] += 1
	else:
		for i in range(n):
			if k == 0:
				for j in str[i:]:
					if j == '1':
						ans += '0'
					else:
						ans += '1'
				break
			if str[i] == '1':
				k -= 1
				ans += '1'
				indexes[i] += 1
			else:
				ans += '1'
	if k % 2 == 1:
		if ans[-1] == '0':
			ans = ans[:-1] + '1'
		else:
			ans = ans[:-1] + '0'
	indexes[-1] += k
	print(ans)
	print(*indexes)


import math as m
i = input()
inp = []
for a in range(0, int(i)):
	inp.append([[int(x) for x in input().split()], [int(x) for x in list(input())]])
for [[n, k], arr] in inp:
	if k % 2 == 1:
		arr = [1 - x for x in arr]
	indices = n * [0]
	rem = k
	pos = 0
	while rem > 0 and pos <= n - 1:
		if arr[pos] == 0:
			indices[pos] += 1
			arr[pos] = 1 - arr[pos]
			rem -= 1
		pos += 1
	indices[-1] += rem
	if rem % 2 == 1:
		arr[-1] = 1 - arr[-1]
	print(''.join([str(x) for x in arr]))
	print(' '.join([str(x) for x in indices]))


t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	s = list(input())
	used = 0
	op = []
	for (i, v) in enumerate(s):
		if used % 2:
			if s[i] == '1':
				s[i] = '0'
			else:
				s[i] = '1'
			if v == '1':
				v = '0'
			else:
				v = '1'
		if i == len(s) - 1:
			op += [k]
			break
		if k > 0:
			if v == '1' and k % 2:
				k -= 1
				used += 1
				op += [1]
			elif v == '0' and k % 2 == 0:
				k -= 1
				used += 1
				op += [1]
			else:
				op += [0]
			(s[i], v) = ('1', '1')
	while len(op) < n:
		op += [0]
	for i in range(len(op)):
		op[i] = str(op[i])
	op = ' '.join(op)
	print(''.join(s))
	print(op)


for _ in [0] * int(input()):
	(n, k0) = map(int, input().split())
	s = input()
	i = 0
	k = k0
	y = [0] * n
	if k % 2 == 0:
		z = 0
		fe = 1
		fo = 0
	else:
		z = 1
		fo = 1
		fe = 0
	while k > 0 and i < n - 1:
		if s[i] == '1':
			y[i] = z
			k = k - fo
		else:
			k = k - fe
			y[i] = 1 - z
		i = i + 1
	b = '1' * i
	if k > 0:
		y[n - 1] = k
		if (k0 - k) % 2 == 1:
			b = b + str(1 - int(s[n - 1]))
		else:
			b = b + s[n - 1]
	elif k0 % 2 == 1:
		for j in s[i:]:
			b = b + str(1 - int(j))
	else:
		b = b + s[i:]
	if k0 == 0:
		b = s
	print(b)
	print(*y)


from sys import stdin
input = stdin.readline
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input().strip()
	ans = ''
	aa = []
	left = k
	for i in range(n):
		if k % 2 == 1:
			if s[i] == '1':
				if left:
					left -= 1
					ans += '1'
					aa.append(1)
				else:
					ans += '0'
					aa.append(0)
			else:
				ans += '1'
				aa.append(0)
		elif s[i] == '1':
			ans += '1'
			aa.append(0)
		elif left:
			left -= 1
			ans += '1'
			aa.append(1)
		else:
			ans += '0'
			aa.append(0)
	ans = ans[:-1] + str((int(ans[-1]) + left) % 2)
	aa[-1] += left
	print(ans)
	print(*aa)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	ans = [0] * n
	fin = [0] * n
	s = input().strip()
	arr = []
	for e in s:
		arr.append(int(e))
	cng = 0
	i = 0
	for ele in arr:
		cur = 0
		if cng % 2 != 0:
			if ele == 0:
				cur = 1
		elif ele == 1:
			cur = 1
		if k == 0:
			fin[i] = cur
		else:
			if i == n - 1:
				ans[n - 1] = k
				fin[i] = cur
				break
			if cur == 1:
				if k % 2 == 0:
					ans[i] = 0
				else:
					ans[i] = 1
					cng += 1
					k -= 1
				fin[i] = 1
			else:
				if k % 2 != 0:
					ans[i] = 0
				else:
					ans[i] = 1
					cng += 1
					k -= 1
				fin[i] = 1
		i += 1
	print(''.join(list(map(str, fin))))
	print(' '.join(list(map(str, ans))))


cases = int(input())
while cases:
	cases -= 1
	(n, k) = map(int, input().split())
	s = input()
	i = 0
	sol = [0] * n
	kk = k
	for i in range(len(s)):
		if k == 0:
			break
		if kk % 2 == 1 and s[i] == '1':
			sol[i] += 1
			k -= 1
		elif kk % 2 == 0 and s[i] == '0':
			sol[i] += 1
			k -= 1
	sol[n - 1] += k
	ret = ''
	for i in range(n):
		flip = kk - sol[i]
		if flip % 2 == 0:
			ret += s[i]
		elif s[i] == '1':
			ret += '0'
		else:
			ret += '1'
	print(ret)
	printsol = ''
	for i in sol:
		printsol += str(i) + ' '
	print(printsol)


import math, bisect, heapq, random, sys, itertools
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline

def gprint(t, ans=''):
	print(f'Case #{t + 1}:', ans)
ints = lambda : list(map(int, input().split()))
alpha = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
p2 = [1]
p = 10 ** 9 + 7
ANS = []
for t in range(int(input())):
	(n, k) = ints()
	m = k
	a = input().strip()
	ans = [0] * n
	res = ''
	v = 0
	for i in range(n):
		if k == 0:
			break
		if a[i] == '1':
			if m % 2 == 1:
				ans[i] = 1
				k -= 1
		elif m % 2 == 0:
			ans[i] = 1
			k -= 1
		res += '1'
	if k:
		ans[-1] += k
		if k % 2:
			v = 1
	for i in range(len(res), n):
		if m % 2 == 0:
			res += a[i]
		elif a[i] == '1':
			res += '0'
		else:
			res += '1'
	if v:
		if res[-1] == '1':
			res = res[:-1] + '0'
		else:
			res = res[:-1] + '1'
	print(res)
	print(*ans)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	s = input()
	res = list()
	for x in s:
		res.append(x)
	if b % 2 == 1:
		for i in range(a):
			if res[i] == '1':
				res[i] = '0'
			else:
				res[i] = '1'
	ans = [0 for i in range(a)]
	for i in range(a):
		if res[i] == '0' and b > 0:
			res[i] = '1'
			ans[i] += 1
			b -= 1
	if b > 0:
		if b % 2 == 1:
			if res[a - 1] == '1':
				res[a - 1] = '0'
			else:
				res[a - 1] = '1'
		ans[a - 1] += b
	print(''.join(res))
	print(*ans)


I = lambda : [int(i) for i in input().split()]
for _ in range(I()[0]):
	(n, k) = I()
	s = input()
	if k % 2:
		s = [{'0': '1', '1': '0'}[i] for i in s]
	(l, ns) = (n * [0], '')
	for (i, v) in list(enumerate(s))[:-1]:
		if v == '0' and k > 0:
			ns += '1'
			l[i] = 1
			k -= 1
		else:
			ns += v
	l[-1] = k
	ns += {'0': '1', '1': '0'}[s[-1]] if k % 2 else s[-1]
	print(ns)
	print(*l)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	bits = list(input())
	flips = [0] * len(bits)
	used_flips = 0
	for j in range(n):
		b = bits[j]
		if used_flips < k:
			if j < n - 1:
				if b == '0':
					if k % 2 == 0:
						flips[j] = 1
						used_flips += 1
				elif k % 2 == 1:
					flips[j] = 1
					used_flips += 1
			else:
				flips[j] = k - used_flips
		if (k - flips[j]) % 2 == 1:
			bits[j] = str(1 - int(bits[j]))
	print(''.join([str(x) for x in bits]))
	print(' '.join([str(x) for x in flips]))


import sys
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
for tc in range(int(input())):
	(n, k) = I()
	ar = list(input().strip())
	temp = [0] * n
	if k % 2 == 0:
		if ar[0] == '0' and k:
			k -= 1
			temp[0] = 1
		for i in range(1, n):
			if k and ar[i] == '0':
				k -= 1
				temp[i] += 1
			elif not k:
				break
		temp[-1] += k
	else:
		if ar[0] == '1':
			k -= 1
			temp[0] = 1
		for i in range(1, n):
			if k and ar[i] == '1':
				k -= 1
				temp[i] += 1
			elif not k:
				break
		temp[-1] += k
	now = sum(temp)
	ans = [''] * n
	for i in range(n):
		if (now - temp[i]) % 2:
			ans[i] = '1' if ar[i] == '0' else '0'
		else:
			ans[i] = ar[i]
	print(''.join(ans))
	print(*temp)


addy = int(input())
for k in range(addy):
	(n, o) = map(int, input().split())
	s = input()
	out = ''
	l = []
	if o % 2:
		for i in range(n):
			if o >= 1 and s[i] == '1' and (i != n - 1):
				out += '1'
				o -= 1
				l.append(1)
			elif o >= 1 and i == n - 1:
				if o % 2:
					if s[i] == '1':
						out += '1'
					else:
						out += '0'
				elif s[i] == '1':
					out += '0'
				else:
					out += '1'
				l.append(o)
				o = 0
			elif o == 0:
				if s[i] == '1':
					out += '0'
				else:
					out += '1'
				l.append(0)
			else:
				out += '1'
				l.append(0)
	else:
		for i in range(n):
			if o >= 1 and s[i] == '0' and (i != n - 1):
				out += '1'
				o -= 1
				l.append(1)
			elif o >= 1 and i == n - 1:
				if o % 2:
					if s[i] == '1':
						out += '0'
					else:
						out += '1'
				elif s[i] == '1':
					out += '1'
				else:
					out += '0'
				l.append(o)
				o = 0
			elif o == 0:
				out += s[i]
				l.append(0)
			else:
				out += '1'
				l.append(0)
	print(out)
	print(*l)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	a = []
	for j in s:
		a.append(j)
	l = [0] * n
	c = 0
	for j in range(n):
		if c < k and (a[j] == '1' and k % 2 == 1):
			l[j] += 1
			c += 1
			a[j] = '1'
		elif c < k and (a[j] == '0' and k % 2 == 0):
			l[j] += 1
			c += 1
			a[j] = '1'
		elif a[j] == '0' and k % 2 == 1:
			a[j] = '1'
		elif a[j] == '1' and k % 2 == 1:
			a[j] = '0'
	d = k - c
	if d % 2 == 1:
		if a[-1] == '1':
			a[-1] = '0'
		else:
			a[-1] = '1'
		l[-1] += d
	else:
		l[-1] += d
	print(''.join(a))
	print(*l)


from sys import stdin
input = stdin.readline
for test in range(int(input())):
	(n, k) = map(int, input().split())
	res = [0] * n
	s = input()
	kc = k
	if k & 1:
		i = 0
		while k:
			if i == n - 1:
				res[i] = k
				break
			if s[i] == '1':
				res[i] = 1
				k -= 1
			i += 1
	else:
		i = 0
		while k:
			if i == n - 1:
				res[i] = k
				break
			if s[i] == '0':
				res[i] = 1
				k -= 1
			i += 1
	sn = ''
	for i in range(n):
		if kc - res[i] & 1:
			if s[i] == '0':
				sn += '1'
			else:
				sn += '0'
		else:
			sn += s[i]
	print(sn)
	print(*res)


import time
from sys import stdin
input = stdin.readline
time.sleep(15 * 10 ** (-3))
for test in range(int(input())):
	(n, k) = map(int, input().split())
	res = [0] * n
	s = input()
	kc = k
	if k & 1:
		i = 0
		while k:
			if i == n - 1:
				res[i] = k
				break
			if s[i] == '1':
				res[i] = 1
				k -= 1
			i += 1
	else:
		i = 0
		while k:
			if i == n - 1:
				res[i] = k
				break
			if s[i] == '0':
				res[i] = 1
				k -= 1
			i += 1
	sn = ''
	for i in range(n):
		if kc - res[i] & 1:
			if s[i] == '0':
				sn += '1'
			else:
				sn += '0'
		else:
			sn += s[i]
	print(sn)
	print(*res)


def solve():
	(n, k) = map(int, input().split())
	s = input()
	rs = list(s)
	nk = k
	if k % 2 == 1:
		rs = ['1' if i == '0' else '0' for i in rs]
	ans = [0 for _ in range(n)]
	lt = 0
	for i in range(n):
		if k == 0:
			break
		if s[i] == '0':
			if nk % 2 == 0:
				ans[i] = 1
				k -= 1
		elif nk % 2 == 1:
			ans[i] = 1
			k -= 1
		lt += 1
	ans[-1] += k
	change = [True if (nk - ans[i]) % 2 == 1 else False for i in range(n)]
	ns = [s[i] if change[i] == False else '1' if s[i] == '0' else '0' for i in range(n)]
	print(''.join(ns))
	print(*ans, sep=' ')
tc = int(input())
for _ in range(tc):
	solve()


t = int(input())
for qwer in range(t):
	(n, k) = map(int, input().split())
	sp = list(input())
	sp = list(map(int, sp))
	ch = False
	if k % 2 == 0:
		ch = True
	otv = [0] * n
	for i in range(n):
		if sp[i] == 0 and ch and (k > 0):
			otv[i] = 1
			sp[i] = 1
			k -= 1
		elif sp[i] == 1 and (not ch) and (k > 0):
			otv[i] = 1
			sp[i] = 1
			k -= 1
		elif sp[i] == 0 and ch and (k <= 0):
			sp[i] = 0
			k -= 1
		elif sp[i] == 1 and (not ch) and (k <= 0):
			sp[i] = 0
			k -= 1
		else:
			sp[i] = 1
	if k > 0 and k % 2 == 0:
		otv[-1] += k
	elif k > 0 and k % 2 == 1:
		otv[-1] += k
		sp[-1] = 0
	print(''.join(list(map(str, sp))))
	print(*otv)


tc = int(input())
for _ in range(tc):
	(n, k) = list(map(int, input().split()))
	s = list(input())
	ans = [0] * n
	t = k
	for i in range(n):
		c = int(s[i])
		if k & 1 == c & 1:
			if t != 0:
				ans[i] = 1
				s[i] = '1'
				t -= 1
			else:
				s[i] = '0'
		else:
			s[i] = '1'
	if t != 0:
		ans[n - 1] += t
		if t % 2 != 0:
			s[n - 1] = '0'
	print(''.join(s))
	for i in ans:
		print(i, end=' ')
	print()


for test in range(int(input())):
	(n, k) = map(int, input().split())
	res = [0] * n
	s = input()
	kc = k
	if k & 1:
		i = 0
		while k:
			if i == n - 1:
				res[i] = k
				break
			if s[i] == '1':
				res[i] = 1
				k -= 1
			i += 1
	else:
		i = 0
		while k:
			if i == n - 1:
				res[i] = k
				break
			if s[i] == '0':
				res[i] = 1
				k -= 1
			i += 1
	sn = ''
	for i in range(n):
		if kc - res[i] & 1:
			if s[i] == '0':
				sn += '1'
			else:
				sn += '0'
		else:
			sn += s[i]
	print(sn)
	print(*res)


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


t = int(input())

def f(n, k, s):
	arr = [0 for i in range(n)]
	f_sum = 0
	s_new = ''
	for i in range(len(s)):
		if s[i] + k % 2 != 1 and f_sum < k:
			arr[i] += 1
			f_sum += 1
			s_new += '1'
		elif k % 2 == 0:
			s_new += str(s[i])
		elif s[i] == 1:
			s_new += '0'
		else:
			s_new += '1'
	if f_sum != k:
		arr[-1] += k - f_sum
		s_new = s_new[:len(s_new) - 1]
		if (k - arr[-1]) % 2 != 0:
			if s[-1] == 0:
				s_new += '1'
			else:
				s_new += '0'
		else:
			s_new += str(s[-1])
	print(s_new)
	for i in arr:
		print(i, end=' ')
	print('')
for i in range(t):
	line = [int(j) for j in input().split()]
	n = line[0]
	k = line[1]
	s = [int(j) for j in input()]
	f(n, k, s)


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

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

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

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

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

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

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

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

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

def main():
	how_much_noob_I_am = 1
	how_much_noob_I_am = inpu()
	for _ in range(how_much_noob_I_am):
		(n, k) = sep()
		s = list(inp())
		r = [0] * n
		copy = k
		for i in range(n):
			if k == 0:
				break
			if copy % 2 == 1 and s[i] == '1':
				k -= 1
				r[i] += 1
			elif copy % 2 == 0 and s[i] == '0':
				k -= 1
				r[i] += 1
		ans = ''
		r[-1] += k
		k = copy
		for i in range(n):
			tot = k - r[i]
			if tot % 2 == 0:
				ans += s[i]
			else:
				ans += str(int(s[i]) ^ 1)
		print(ans)
		print(*r)
main()


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input().rstrip()
	kc = k
	f = [0] * n
	for i in range(n):
		if k == 0:
			break
		elif kc % 2 == 0 and s[i] == '0':
			f[i] += 1
			k -= 1
		elif kc % 2 == 1 and s[i] == '1':
			f[i] += 1
			k -= 1
	f[n - 1] += k
	ans = ''
	for i in range(n):
		flip = kc - f[i]
		if flip % 2 == 0:
			ans += s[i]
		elif s[i] == '0':
			ans += '1'
		else:
			ans += '0'
	print(ans)
	print(*f)


loopcount = int(input())
for loop in range(loopcount):
	x = input()
	x = x.split(' ')
	x = list(map(int, x))
	s = input()
	s = list(s)
	movesLeft = x[1]
	odd = True
	if x[1] % 2 == 0:
		odd = False
	output = ''
	sequence = [0] * x[0]
	for i in range(x[0]):
		if movesLeft == 0:
			break
		if odd and s[i] == '1':
			sequence[i] += 1
			movesLeft -= 1
		if not odd and s[i] == '0':
			sequence[i] += 1
			movesLeft -= 1
	sequence[x[0] - 1] += movesLeft
	if not odd:
		for i in range(x[0]):
			if sequence[i] % 2 == 1:
				if s[i] == '1':
					output += '0'
				else:
					output += '1'
			else:
				output += s[i]
	if odd:
		for i in range(x[0]):
			if sequence[i] % 2 == 0:
				if s[i] == '1':
					output += '0'
				else:
					output += '1'
			else:
				output += s[i]
	print(output)
	for i in range(x[0]):
		print(sequence[i], end=' ')
	print()


import math
from collections import defaultdict
t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	s = input()
	ans = ''
	lis = []
	tot = []
	if k % 2 == 1:
		for j in range(0, len(s)):
			if k > 0 and s[j] == '1':
				tot.append(1)
				k -= 1
			else:
				tot.append(0)
		if k > 0:
			tot[-1] = tot[-1] + k
		final = ''
		for j in range(0, len(s)):
			if s[j] == '1':
				if tot[j] % 2 == 1:
					final = final + '1'
				else:
					final = final + '0'
			elif tot[j] % 2 == 0:
				final = final + '1'
			else:
				final = final + '0'
		print(final)
		for j in tot:
			print(j, end=' ')
		print()
	else:
		for j in range(0, len(s)):
			if k > 0 and s[j] == '0':
				tot.append(1)
				k -= 1
			else:
				tot.append(0)
		if k > 0:
			tot[-1] = tot[-1] + k
		final = ''
		for j in range(0, len(s)):
			if s[j] == '1':
				if tot[j] % 2 == 0:
					final = final + '1'
				else:
					final = final + '0'
			elif tot[j] % 2 == 1:
				final = final + '1'
			else:
				final = final + '0'
		print(final)
		for j in tot:
			print(j, end=' ')
		print()


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


from math import ceil

def solve(s):
	pass
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	f = [0] * n
	tf = k
	for i in range(n):
		if k == 0:
			break
		elif tf % 2 == 0 and s[i] == '0':
			f[i] += 1
			k -= 1
		elif tf % 2 != 0 and s[i] == '1':
			f[i] += 1
			k -= 1
	f[n - 1] += k
	ans = ''
	for i in range(n):
		flips = tf - f[i]
		if flips % 2 == 0:
			ans += s[i]
		elif s[i] == '1':
			ans += '0'
		else:
			ans += '1'
	print(ans)
	print(*f)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	ans = [0] * n
	kc = k
	for i in range(n):
		if k == 0:
			break
		if kc & 1 == 1 and s[i] == '1':
			ans[i] += 1
			k -= 1
		elif kc & 1 == 0 and s[i] == '0':
			ans[i] += 1
			k -= 1
	ans[n - 1] += k
	an2 = ''
	for i in range(n):
		fl = kc - ans[i]
		if fl & 1 == 0:
			an2 += s[i]
		elif s[i] == '0':
			an2 += '1'
		else:
			an2 += '0'
	print(an2)
	print(*ans)


t = int(input())

def solve(n, k, bits):
	if k % 2 == 0:
		selected = [0 for i in range(n)]
		final = [i for i in bits]
		for i in range(n):
			if k == 0:
				return (selected, final)
			elif final[i] == 0:
				k -= 1
				selected[i] += 1
				final[i] += 1
		selected[-1] += k
		if k % 2 == 1:
			final[-1] = 0
		return (selected, final)
	if k % 2 == 1:
		selected = [0 for i in range(n)]
		final = [1 - i for i in bits]
		for i in range(n):
			if k == 0:
				return (selected, final)
			elif final[i] == 0:
				k -= 1
				selected[i] += 1
				final[i] += 1
		selected[-1] += k
		if k % 2 == 1:
			final[-1] = 0
		return (selected, final)
for i in range(t):
	(n, k) = [int(i) for i in input().split()]
	bits = [int(i) for i in input()]
	(selected, final) = solve(n, k, bits)
	final_str = ''
	for i in range(len(final)):
		final_str += str(final[i])
	print(final_str)
	print(*selected)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	lst = input()
	count = [0] * n
	index = 0
	inverted = False
	ans = ''
	while index < n and k > 0:
		if lst[index] == '1' and inverted == False or (lst[index] == '0' and inverted):
			if k % 2 == 0:
				index += 1
			else:
				k -= 1
				if inverted:
					inverted = False
				else:
					inverted = True
				count[index] += 1
				index += 1
			ans += '1'
		else:
			if k % 2 != 0:
				index += 1
			else:
				k -= 1
				if inverted:
					inverted = False
				else:
					inverted = True
				count[index] += 1
				index += 1
			ans += '1'
	if len(ans) == n:
		count[-1] += k
		if k % 2 != 0:
			x = ans[:n - 1]
			if ans[-1] == '1':
				x += '0'
			else:
				x += '1'
			ans = x
	else:
		for i in range(index, n):
			if lst[i] == '1' and inverted == False or (lst[i] == '0' and inverted):
				ans += '1'
			else:
				ans += '0'
	print(ans)
	for i in count:
		print(i, end=' ')
	print()


t = int(input())
while t > 0:
	c = input().split()
	(n, k) = (int(c[0]), int(c[1]))
	a = input()
	b = [0 for i in range(n)]
	if k % 2 == 0:
		cur = 0
		i = 0
		while cur < k and i < n:
			if i == n - 1:
				b[i] = k - cur
			elif a[i] == '0':
				b[i] = 1
				cur += 1
			i += 1
	else:
		cur = 0
		i = 0
		while cur < k and i < n:
			if i == n - 1:
				b[i] = k - cur
			elif a[i] == '1':
				b[i] = 1
				cur += 1
			i += 1
	ans = ''
	for i in range(n):
		if (k + b[i]) % 2:
			if a[i] == '0':
				ans += '1'
			else:
				ans += '0'
		else:
			ans += a[i]
	print(ans)
	print(*b, sep=' ')
	t -= 1


for iiii in range(int(input())):
	(n, m) = map(int, input().split())
	q = input()
	q1 = [0 for i in range(n)]
	summ = m
	for i in range(n):
		if summ > 0:
			if q[i] == '1' and m % 2 == 1:
				q1[i] += 1
				summ -= 1
			elif q[i] == '0' and m % 2 == 0:
				q1[i] += 1
				summ -= 1
	if summ > 0:
		if summ % 2 == 0:
			q1[n - 1] += summ
		elif n == 1:
			q1[0] += summ
		else:
			q1[n - 1] += 1
			q1[n - 1] = q1[n - 1] + summ - 1
	qwe = ''
	for i in range(n):
		if q[i] == '0':
			if (m - q1[i]) % 2 == 0:
				qwe = qwe + '0'
			else:
				qwe = qwe + '1'
		elif q[i] == '1':
			if (m - q1[i]) % 2 == 0:
				qwe = qwe + '1'
			else:
				qwe = qwe + '0'
	print(qwe)
	print(*q1)


def rev(b):
	b_ = ''
	for c in b:
		if c == '1':
			b_ += '0'
		else:
			b_ += '1'
	return b_

def printm(b, arr):
	for c in range(len(b)):
		print(b[c] if arr[c] % 2 == 0 else rev(b[c]), end='')
for i in range(int(input())):
	(n, k) = map(int, input().split())
	b = input()
	if k % 2 == 1:
		b = rev(b)
	count = 0
	arr = [0 for j in range(n)]
	for c in range(n):
		if count == k:
			break
		if b[c] == '0':
			count += 1
			arr[c] += 1
	arr[-1] += k - count
	printm(b, arr)
	print()
	print(' '.join([str(q) for q in arr]))


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split(' '))
	K = k
	s = input()
	ans = [0] * n
	for j in range(n):
		if k == 0:
			break
		if j == n - 1:
			ans[j] = k
			continue
		if s[j] == '1':
			if K % 2:
				ans[j] += 1
				k -= 1
				if k == 0:
					break
		elif K % 2 == 0:
			ans[j] += 1
			k -= 1
			if k == 0:
				break
	res = ''
	for j in range(n):
		if s[j] == '1':
			if (K - ans[j]) % 2 == 0:
				res += '1'
			else:
				res += '0'
		elif (K - ans[j]) % 2 == 0:
			res += '0'
		else:
			res += '1'
	print(res)
	for j in ans:
		print(j, end=' ')
	print()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = input()
	(k2, i, res, res2) = (k, 0, [], [0] * n)
	b = ['0', '1']
	if k % 2:
		for x in a[:n - 1]:
			if k2 == 0:
				break
			if x == '1':
				k2 -= 1
				res2[i] = 1
			res += [1]
			i += 1
		if k2 == 0:
			res += [b[y != '1'] for y in a[i:]]
		else:
			dif = k - k2
			if dif % 2:
				res += [b[a[-1] != '1']]
				res2[-1] = k2
			else:
				res += [a[-1]]
				res2[-1] = k2
	else:
		for x in a[:n - 1]:
			if k2 == 0:
				break
			if x == '0':
				k2 -= 1
				res2[i] = 1
			res += ['1']
			i += 1
		if k2 == 0:
			res += [y for y in a[i:]]
		else:
			dif = k - k2
			if dif % 2:
				res += [b[a[-1] != '1']]
			else:
				res += [a[-1]]
			res2[-1] = k2
	print(*res, sep='')
	print(*res2, sep=' ')


from math import ceil
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(input())
	l = [0] * n
	c = 0
	for i in range(n):
		if c < k and (s[i] == '1' and k & 1 or (s[i] == '0' and (not k & 1))):
			l[i] += 1
			c += 1
			s[i] = chr(ord(s[i]) ^ (k & 1 ^ 1))
		else:
			s[i] = chr(ord(s[i]) ^ k & 1)
	for i in range(n):
		if s[i] == '0' or i == n - 1:
			l[i] += k - c
			if k - c & 1:
				s[i] = chr(ord(s[i]) ^ 1)
	print(''.join(s))
	print(*l)


n = int(input())
for i in range(n):
	(lent, moves) = list(map(int, input().split(' ')))
	s = input()
	l1 = [0] * lent
	l2 = []
	moves1 = moves
	for i in range(len(s)):
		l2.append(s[i])
	flag = 0
	for i in range(len(s)):
		num = s[i]
		if flag % 2 == 1:
			if s[i] == '1':
				num = '0'
			else:
				num = '1'
		if moves > 0:
			if i == lent - 1:
				l2[i] = num
				l1[i] = moves
			elif moves % 2 == 0:
				if num == '0':
					l2[i] = '1'
					moves -= 1
					flag += 1
					l1[i] = 1
				else:
					l2[i] = '1'
			elif moves % 2 == 1:
				if num == '1':
					l2[i] = '1'
					moves -= 1
					flag += 1
					l1[i] = 1
				else:
					l2[i] = '1'
		else:
			l2[i] = num
	print(''.join(l2))
	for k in l1:
		print(k, end=' ')
	print()


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


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	ans = [0] * n
	p = k % 2
	i = 0
	while k > 0 and i < n:
		if int(s[i]) == p:
			ans[i] += 1
			k -= 1
		i += 1
	ans[-1] += k
	r = ''
	for i in range(n):
		if ans[i] % 2 != p:
			r += str((int(s[i]) + 1) % 2)
		else:
			r += s[i]
	print(r)
	print(*ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	flip = [0] * n
	change = 0
	ans = ''
	temp = k
	for i in range(n):
		if k == 0:
			flip[i] = k
			break
		else:
			if change % 2 == 0:
				ch = s[i]
			elif s[i] == '1':
				ch = '0'
			else:
				ch = '1'
			if i == n - 1:
				ans += ch
				flip[i] = k
				k = 0
			elif ch == '0' and k % 2 == 0 or (ch == '1' and k % 2 == 1):
				change += 1
				flip[i] = 1
				k -= 1
				ans += '1'
			elif ch == '1' and k % 2 == 0 or (ch == '0' and k % 2 == 1):
				flip[i] = 0
				ans += '1'
	temp = len(ans)
	for i in range(temp, n):
		if change % 2 == 0:
			ans += s[i]
		elif s[i] == '1':
			ans += '0'
		else:
			ans += '1'
	print(ans)
	for val in flip:
		print(val, end=' ')
	print()


for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	ki = k
	seq = input()
	seq = [int(i) for i in seq]
	act = [0 for i in range(n)]
	ans = []
	for i in seq:
		if ki % 2 == 0 and i == 0:
			ans.append(0)
		elif ki % 2 != 0 and i != 0:
			ans.append(0)
		else:
			ans.append(1)
	i = 0
	while k > 0 and i < len(seq):
		if ki % 2 == 0:
			if seq[i] != 1:
				k -= 1
				act[i] += 1
			ans[i] = 1
		else:
			if seq[i] == 1:
				k -= 1
				act[i] += 1
			ans[i] = 1
		i += 1
	if k != 0:
		if k % 2 == 0:
			act[-1] += k
		else:
			act[-1] += k
			ans[-1] = 0 if ans[-1] == 1 else 0
	print(''.join([str(i) for i in ans]))
	print(*act)


for test in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	f = k
	op = []
	for i in range(n - 1):
		if k > 0:
			if s[i] == '1':
				if f % 2 == 1:
					k -= 1
					op.append(1)
				else:
					op.append(0)
			elif f % 2 == 0:
				k -= 1
				op.append(1)
			else:
				op.append(0)
			print('1', end='')
		else:
			if s[i] == '1':
				if f % 2 == 1:
					print('0', end='')
				else:
					print('1', end='')
			elif f % 2 == 1:
				print('1', end='')
			else:
				print('0', end='')
			op.append(0)
	if s[-1] == '1':
		if (f - k) % 2 == 0:
			print('1')
		else:
			print('0')
	elif (f - k) % 2 == 1:
		print('1')
	else:
		print('0')
	op.append(k)
	print(*op)


def solve():
	(n, k) = map(int, input().split())
	m = k
	s = list(input())
	f = [0 for _ in range(n)]
	for i in range(n):
		if k == 0:
			break
		if m % 2 == 0 and s[i] == '0' or (m % 2 == 1 and s[i] == '1'):
			f[i] = 1
			k -= 1
	f[-1] += k
	for i in range(n):
		if (m ^ f[i]) & 1:
			if s[i] == '0':
				s[i] = '1'
			else:
				s[i] = '0'
	print(*s, sep='')
	print(*f)
t = int(input())
while t > 0:
	t -= 1
	solve()


N = int(input())
for i in range(N):
	(n, k) = map(int, input().split())
	s = [int(n) for n in input()]
	ll = [0] * n
	kc = k
	ans = ''
	for i in range(n):
		if k == 0:
			break
		if kc % 2 and s[i]:
			ll[i] += 1
			k -= 1
		elif not kc % 2 and (not s[i]):
			ll[i] += 1
			k -= 1
	ll[n - 1] += k
	for i in range(n):
		flip = kc - ll[i]
		if not flip % 2:
			ans += str(1 if s[i] else 0)
		else:
			ans += str(1 if not s[i] else 0)
	print(ans)
	for i in ll:
		print(i, end=' ')
	print()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(map(int, input()))
	S = s.copy()
	res = [0 for i in range(n)]
	o = 0
	O = k
	i = 0
	while i < n and k > 0:
		s[i] ^= o
		if k % 2 != s[i] or i == n - 1:
			i += 1
			continue
		res[i] += 1
		k -= 1
		o ^= 1
		i += 1
	res[-1] += k
	for i in range(n):
		if (O - res[i]) % 2:
			S[i] ^= 1
	ans = ''
	for i in S:
		ans += str(i)
	print(ans)
	print(*res)


import sys
cases = int(input())
for case in range(cases):
	(n, k) = map(int, input().split())
	string = []
	for i in range(n):
		digit = sys.stdin.read(1)
		string.append(int(digit))
	if k % 2 != 0:
		for i in range(n):
			if string[i] == 0:
				string[i] = 1
			else:
				string[i] = 0
	flips = [0] * n
	for i in range(n):
		if string[i] == 0 and k:
			flips[i] += 1
			string[i] = 1
			k -= 1
	flips[-1] += k
	if k % 2 != 0:
		string[-1] = 0
	print(*string, sep='')
	print(*flips)
	sys.stdin.readline()


I = input
for _ in [0] * int(I()):
	(n, k) = map(int, I().split())
	a = [int(x) ^ k & 1 for x in I()]
	b = [0] * n
	i = 0
	while (n - i) * k:
		b[i] = a[i] ^ 1
		a[i] = 1
		k -= b[i]
		i += 1
	a[-1] ^= k & 1
	b[-1] += k
	print(*a, sep='')
	print(*b)


from xmlrpc.client import boolean
for _ in range(int(input())):
	(n, k) = (int(x) for x in input().split())
	s = input()
	s = list(s)
	l = n * [0]
	tmp = k
	if k % 2 == 1:
		for i in range(n - 1):
			if s[i] == '1' and tmp != 0:
				l[i] += 1
				tmp -= 1
		if tmp != 0:
			l[n - 1] += tmp
		for i in range(n):
			if l[i] % 2 == 1:
				continue
			elif s[i] == '0':
				s[i] = '1'
			else:
				s[i] = '0'
	else:
		for i in range(n - 1):
			if s[i] == '0' and tmp != 0:
				l[i] += 1
				tmp -= 1
		if tmp != 0:
			l[n - 1] += tmp
		for i in range(n):
			if l[i] % 2 == 0:
				continue
			elif s[i] == '0':
				s[i] = '1'
			else:
				s[i] = '0'
	''.join((str(i) for i in s))
	print(*s, sep='')
	print(*l)


def test():
	line = input()
	(N, K) = line.split(' ')
	n = int(N)
	k = int(K)
	s = input()
	v = []
	a = 0
	for i in range(0, n):
		v.append(0)
	for i in range(0, n):
		if k == 0:
			break
		if k % 2 == 0:
			if a % 2 == 0:
				if s[i] == '0':
					v[i] += 1
					k -= 1
					a += 1
			elif s[i] == '1':
				v[i] += 1
				k -= 1
				a += 1
		elif a % 2 == 0:
			if s[i] == '1':
				v[i] += 1
				k -= 1
				a += 1
		elif s[i] == '0':
			v[i] += 1
			k -= 1
			a += 1
	rem = k
	if k > 0:
		k = int(K)
		if (k - v[0]) % 2 == 0:
			if v[0] == '1':
				v[0] += rem
			else:
				v[n - 1] += rem
		elif v[0] == '0':
			v[0] += rem
		else:
			v[n - 1] += rem
	k = int(K)
	for i in range(0, n):
		if (k - v[i]) % 2 == 0:
			print(s[i], end='')
		elif s[i] == '0':
			print('1', end='')
		else:
			print('0', end='')
	print()
	for i in v:
		print(i, end=' ')
	print()
t = int(input())
while t != 0:
	test()
	t -= 1


import collections
import math
import sys
need_two = 0

def main():
	(n, k) = map(int, input().split())
	bit = list(map(int, list(str(input()))))
	d = [0] * n
	b = k % 2
	for i in range(n):
		if bit[i] == b and k > 0:
			bit[i] ^= 1
			k -= 1
			d[i] = 1
		else:
			d[i] = 0
	if k % 2 == 1:
		bit[n - 1] ^= 1
	d[n - 1] += k
	for i in range(n):
		print(bit[i] ^ b, end='')
	print()
	print(*d)
t = int(input())
while t > 0:
	main()
	t -= 1


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	arr = [int(i) for i in str(input())]
	moves = [0 for i in range(n)]
	if k % 2:
		for i in range(n):
			arr[i] = arr[i] ^ 1
	for i in range(n):
		if k == 0:
			break
		if arr[i] == 0:
			k -= 1
			arr[i] = 1
			moves[i] += 1
	if k and k % 2:
		arr[-1] = 0
		moves[-1] += k
	else:
		moves[-1] += k
	for i in arr:
		print(i, end='')
	print()
	for i in moves:
		print(i, end=' ')
	print()


t = int(input())
for _ in range(t):
	m = input().split()
	ans = 0
	n = int(m[0])
	k = int(m[1])
	a = list(input())
	dic = {}
	for kk in range(n):
		dic[kk] = 0
	if k % 2 == 1:
		for i in range(0, n):
			if a[i] == '1':
				j = i
				break
			else:
				ans = ans + 1
		if ans == n:
			j = n - 1
		for i in range(0, j):
			if a[i] == '1':
				a[i] = '0'
			else:
				a[i] = '1'
		for i in range(j + 1, n):
			if a[i] == '1':
				a[i] = '0'
			else:
				a[i] = '1'
		dic[j] = dic[j] + 1
		k = k - 1
	for s in range(n):
		if a[s] == '0' and k > 0:
			a[s] = '1'
			k = k - 1
			dic[s] = dic[s] + 1
	dic[n - 1] = dic[n - 1] + k
	if k % 2 == 1:
		a[n - 1] = '0'
	for kk in a:
		print(kk, end='')
	print()
	for u in dic.values():
		print(u, end=' ')
	print()


for i in range(int(input())):
	l = list(map(int, input().split()))
	n = l[0]
	k = l[1]
	s = input()
	l = []
	l1 = []
	for j in s:
		l.append(int(j))
		l1.append(0)
	if k % 2 == 1:
		for j in range(n):
			l[j] = 1 - l[j]
	c = 0
	for j in range(n):
		if c == k:
			break
		if l[j] == 0:
			l[j] = 1
			c += 1
			l1[j] = 1
	k -= c
	if k > 0:
		if k % 2 == 1:
			l[-1] = 0
		l1[-1] += k
	for j in l:
		print(j, end='')
	print('\n')
	for j in l1:
		print(j, end=' ')
	print('\n')


for i in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(input())
	for j in range(n):
		s[j] = int(s[j])
	rs = [0] * n
	c = 0
	for j in range(n):
		s[j] = s[j] ^ c % 2
		if not s[j] ^ k % 2 and k:
			rs[j] = 1
			k -= 1
			c += 1
			s[j] = 1
		elif s[j] ^ k % 2:
			s[j] = 1
	rs[-1] += k
	s[-1] = s[-1] ^ k % 2
	for j in s:
		print(j, end='')
	print()
	print(*rs)


def solve():
	(n, k) = map(int, input().split())
	s = input()
	odd = [0 for _ in range(n)]
	original_k = k
	for i in range(n):
		if k == 0:
			break
		if original_k % 2 == 0:
			if s[i] == '1':
				odd[i] = 0
			else:
				odd[i] = 1
				k -= 1
		elif s[i] == '1':
			odd[i] = 1
			k -= 1
		else:
			odd[i] = 0
	extra = k
	odd[-1] += extra
	for i in range(n):
		if (original_k - odd[i]) % 2 == 0:
			print(s[i], end='')
		elif s[i] == '1':
			print('0', end='')
		else:
			print('1', end='')
	print()
	for i in range(n):
		print(odd[i], end='')
		if i == n - 1:
			print()
		else:
			print(' ', end='')
t = int(input())
for _ in range(t):
	solve()