给定一个长度为 $n$ 的字符串 $s_1s_2 \dots s_n$，其中 $s_i \in \{'0', '1', '?'\}$，以及一个整数 $k$。请将所有的 '?' 替换为 '0' 或 '1'，使得满足 $1 \le i < n$ 且 $s_i \neq s_{i+1}$ 的下标 $i$ 的个数恰好等于 $k$。不同的 '?' 可以替换为不同的字符。

为了增加难度，如果存在满足条件的字符串，请找出字典序最小的那一个。

回想一下，对于两个长度为 $n$ 的字符串 $a_1a_2 \dots a_n$ 和 $b_1b_2 \dots b_n$，如果存在一个整数 $k$ ($1 \le k \le n$)，使得对于所有 $1 \le i < k$ 都有 $a_i = b_i$ 且 $a_k < b_k$，则称字符串 $a$ 的字典序小于字符串 $b$。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含两个整数 $n$ 和 $k$ ($1 \le n \le 10^5, 0 \le k < n$)，分别表示字符串的长度和满足条件的下标个数要求。

第二行包含一个字符串 $s_1s_2 \dots s_n$ ($s_i \in \{'0', '1', '?'\}$)。

保证所有测试数据的 $n$ 之和不超过 $10^6$。

输出格式

对于每组测试数据，输出一行。如果存在满足条件的字符串，输出字典序最小的那一个（你需要输出填充完所有 '?' 后的完整字符串，并使其字典序最小）；否则输出 Impossible。

样例

输入 1

5
9 6
1?010??01
9 5
1?010??01
9 6
100101101
9 5
100101101
9 3
????????1

输出 1

100100101
Impossible
100101101
Impossible
000000101