F. Fill the Binary String
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a string $$$s_1s_2...s_n$$$ of length $$$n$$$ where $$$s_i \in \{'0','1','?'\}$$$ and an integer $$$k$$$, please fill out all the $$$'?'$$$ with $$$'0'$$$ or $$$'1'$$$ such that the number of indices $$$i$$$ satisfying $$$1 \leq i \lt n$$$ and $$$s_i \neq s_{i+1}$$$ equals to $$$k$$$.

That's all? Nah! To heat things up,our dear friend asks you to find the answer with the smallest possible lexicographic order if it exists.

Recall that a string $$$a_1 a_2 ...a_n$$$ of length $$$n$$$ is lexicographically smaller than another string $$$b_1 b_2 ...b_n$$$ of length $$$n$$$ if there exists an integer $$$k$$$ ($$$1 \leq k \leq n$$$) such that $$$a_i = b_i$$$ for all $$$1 \leq i \lt k$$$ and $$$a_k \lt b_k$$$ .

Input

There are multiple test cases.

The first line of the input contains an integer $$$T$$$ indicating the number of test cases.

For each test case:

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 10^5 , 0 \leq k \lt n$$$) indicating the length of the string and the required number of indices satisfying the condition.

The second line contains a string $$$s_1s_2...s_n$$$ ($$$s i \in \{'0','1','?'\}$$$).

It's guaranteed that the sum of $$$n$$$ of all test cases will not exceed $$$10^6$$$ .

Output

For each test case output one line.

If the answer exists output the lexicographically smallest one (you need to output the whole given string after filling out all the '?' and make this string the lexicographically smallest); Otherwise output "Impossible" (without quotes).

Example
Input
5
9 6
1?010??01
9 5
1?010??01
9 6
100101101
9 5
100101101
9 3
????????1
Output
100100101
Impossible
100101101
Impossible
000000101