Background

Little Mocha is a genius, especially in string theory, where she has an extraordinary talent. To praise her talent, people often name strings that satisfy certain beautiful properties as “Mocha strings”.

Problem Description

Little H has a binary string $s$ of length $n$ and a positive integer $k$. He defines a binary string $t = t_1 \dots t_m$ of length $m$ to be a Mocha string if and only if $t$ satisfies the following two conditions:

• $s$ is a substring of $t$, i.e., there exist $1 \le l \le r \le m$ such that $s = t_l \dots t_r$;
• There are exactly $k$ substrings of $t$ whose lexicographic order is strictly smaller than $s$. Two substrings are different if and only if they have different lengths or different positions. Formally, there exist exactly $k$ pairs $(l, r)$ such that $1 \le l \le r \le m$ and $t_l \dots t_r$ is lexicographically strictly smaller than $s$.

Since there may be many Mocha strings that satisfy the conditions, Little H wants to find a shortest Mocha string among them. You need to help him find any one of them.

Input Format

This problem contains multiple test cases.

The first line of input contains two non-negative integers $c, t$, representing the test point ID and the number of test cases, respectively. $c = 0$ means this test point is a sample.

Then the test cases follow. For each test case:

• The first line contains two positive integers $n, k$.
• The second line contains a binary string $s$ of length $n$.

Output Format

For each test case, output one line with a binary string, representing any shortest Mocha string. In particular, if no Mocha string exists, output Impossible.

0 5
1 1
1
1 1
0
3 9
101
4 17
1100
4 20
1100

10
Impossible
0101
011100
001100

Hint

Sample 2

See string/string2.in and string/string2.ans in the contestant directory.

This sample satisfies the constraints of test points $4 \sim 6$.

Sample 3

See string/string3.in and string/string3.ans in the contestant directory.

This sample satisfies the constraints of test points $7 \sim 9$.

Sample 4

See string/string4.in and string/string4.ans in the contestant directory.

This sample satisfies the constraints of test points $10 \sim 12$.

Sample 5

See string/string5.in and string/string5.ans in the contestant directory.

This sample satisfies the constraints of test points $13 \sim 15$.

Sample 6

See string/string6.in and string/string6.ans in the contestant directory.

This sample satisfies the constraints of test points $16 \sim 18$.

Sample 7

See string/string7.in and string/string7.ans in the contestant directory.

This sample satisfies the constraints of test points $19, 20$.

Constraints

For all testdata, we have:

• $1 \le t \le 5$;
• $1 \le n \le 200$, $1 \le k \le 3,000$;
• For all $1 \le i \le n$, we have $s_i \in \{0, 1\}$.

::cute-table{tuack}

• Special Property A: If a Mocha string exists, then there exists a Mocha string of length at most $15$.
• Special Property B: For all $1 \le i \le n$, we have $s_i = 0$.
• Special Property C: For all $1 \le i \le n$, we have $s_i = 1$.
• Special Property D: There exists a positive integer $p \in [1,n]$ such that $s_1 = \dots = s_p = 0$ and $s_{p+1} = \dots = s_n = 1$.

Translated by ChatGPT 5