P15650 [NOI Qualifier Joint Contest 2026] Mocha String

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”.

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.

**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$.

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`.

### 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} | Test Point ID | $n \le$ | $k \le$ | Special Property | |:-:|:-:|:-:|:-:| | $1 \sim 3$ | $15$ | $200$ | A | | $4 \sim 6$ | $50$ | $2,000$ | B | | $7 \sim 9$ | ^ | ^ | C | | $10 \sim 12$ | ^ | ^ | D | | $13 \sim 15$ | ^ | $500$ | None | | $16 \sim 18$ | $150$ | $2,000$ | ^ | | $19, 20$ | $200$ | $3,000$ | ^ | - 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