题目描述

Markyyz 正在学习二进制数。他的作业里有一个简单的问题。

给定一个二进制数 $s_{1\sim n}$（$s_{1}$ 是最高位，$s_{n}$ 是最低位）。你需要执行恰好 $k$ 次操作：任意选择一个区间 $[l,r]$ $(1\leq l\leq r\leq n)$，然后翻转 $s_{l},s_{l + 1},\ldots ,s_{r}$，换句话说，对于所有 $i\in [l,r]$，如果 $s_{i}$ 是 $0$ 则变为 $1$，如果 $s_{i}$ 是 $1$ 则变为 $0$。问经过 $k$ 次操作后，能得到的最大的二进制数是多少。

Markyyz 发现无用的算法在这个问题上毫无用处，于是他向 SPY 求助。SPY 起初看轻了这个问题，但最终却得到了 WA（错误答案）。你能帮他们找到正确的解法吗？

输入格式

输入的第一行包含一个整数 $T$ $(1\leq T\leq 6\times 10^{4})$，表示测试用例的数量。

对于每个测试用例：

第一行包含两个整数 $n, k$ $(1\leq n\leq 10^{5},0\leq k\leq 10^{18})$。

第二行包含一个二进制数 $s_{1\sim n}$ （$s_{1} = 1,\forall i\in [2,n]:s_{i}\in \{0,1\}$）。

保证所有测试用例的 $\sum n\leq 2.5\times 10^{6}$。

输出格式

每个测试用例输出一行，一个长度为 $n$ 的字符串，表示经过 $k$ 次操作后能得到的最大二进制数。

2
8 2
10100101
5 233333333333333333
11101

11111101
11111