8965: Binary Number

Markyyz is learning binary numbers. There is an easy problem in his homework.

You are given a binary number �1∼�s1∼n (�1s1 is the highest bit. ��sn is the lowest bit.). You need to do an operation exactly $k$ times: select an interval $[l,r]$ $(1\le l\le r\le n)$ arbitrarily and flip ��,��+1,...,��sl,sl+1,...,sr, in other word, for all $i\in [l,r]$, ��si becomes $1$ if ��si is $0$, ��si becomes $0$ if ��si is $1$. What is the biggest result binary number after the $k$ operations.

Markyyz found useless algorithms useless on the problem, so he asked SPY for help. SPY looked down on the problem but finally got WA (wrong answer). Can you help them to find the right solution?

The first line of the input contains a single integer $T$ (1≤�≤6×104)(1≤T≤6×104), indicating the number of test cases.

In each test case:

The first line contains two integers $n,k$. (1≤�≤105,0≤�≤1018)(1≤n≤105,0≤k≤1018)

The second line contains a binary number �1∼�s1∼n. (�1=1(s1=1, ∀�∈[2,�]:��∈0,1)∀i∈[2,n]:si∈0,1)

It's guarenteed that in all test cases, ∑�≤2.5×106∑n≤2.5×106