#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <map>
#include <cmath>
#include <cstring>
#include <vector>
#include <bitset>
#include <set>

template <typename Tp>
inline void read(Tp &x) {
    x = 0;
    bool f = true; char ch = getchar();
    for ( ; ch < '0' || ch > '9'; ch = getchar()) f ^= ch == '-';
    for ( ; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + (ch ^ 48);
    x = f ? x : -x;
}

const int N = 1e5;

char s[N + 5];
int mn[N + 5][2], mx[N + 5][2], len[N + 5];

int main() {
    int T;
    read(T);
    while (T--) {
        int n, k;
        read(n), read(k);
        scanf("%s", s + 1);
        mn[n][0] = mn[n][1] = mx[n][0] = mx[n][1] = 0;
        for (int i = n - 1; i; --i) {
            if (s[i] == '0' || s[i] == '?') {
                if (s[i + 1] == '0') mn[i][0] = mn[i + 1][0], mx[i][0] = mx[i + 1][0];
                else if (s[i + 1] == '1') mn[i][0] = mn[i + 1][1] + 1, mx[i][0] = mx[i + 1][1] + 1;
                else mn[i][0] = std::min(mn[i + 1][0], mn[i + 1][1] + 1), mx[i][0] = std::max(mx[i + 1][0], mx[i + 1][1] + 1);
            }
            if (s[i] == '1' || s[i] == '?') {
                if (s[i + 1] == '0') mn[i][1] = mn[i + 1][0] + 1, mx[i][1] = mx[i + 1][0] + 1;
                else if (s[i + 1] == '1') mn[i][1] = mn[i + 1][1], mx[i][1] = mx[i + 1][1];
                else mn[i][1] = std::min(mn[i + 1][0] + 1, mn[i + 1][1]), mx[i][1] = std::max(mx[i + 1][0] + 1, mx[i + 1][1]);
            }
        }
        for (int i = 1; i <= n; ++i) printf("%d %d %d %d\n", mn[i][0], mx[i][0], mn[i][1], mx[i][1]);
        std::fill(len + 1, len + n + 1, (s[n] == '?') ? 1 : 2);
        if (s[1] == '?') len[1] = 1;
        int Min, Max;
        if (s[1] == '0') Min = mn[1][0], Max = mx[1][0];
        else if (s[1] == '1') Min = mn[1][1], Max = mx[1][1];
        else Min = std::min(mn[1][0], mn[1][1]), Max = std::max(mx[1][0], mx[1][1]);
        if (k >= Min && k <= Max && (k - Min) % len[1] == 0) {
            int lst = 0;
            for (int i = 1; i <= n; ++i) {
                if (s[i] == '0' || s[i] == '?') {
                    int cost = (i == 1) ? 0 : (lst ^ 0);
                    k -= cost;
                    if (k >= mn[i][0] && k <= mx[i][0] && (k - mn[i][0]) % len[i] == 0) {
                        putchar('0');
                        lst = 0;
                        continue;
                    }
                    else k += cost;
                }
                if (s[i] == '1' || s[i] == '?') {
                    int cost = (i == 1) ? 0 : (lst ^ 1);
                    k -= cost;
                    if (k >= mn[i][1] && k <= mx[i][1] && (k - mn[i][1]) % len[i] == 0) {
                        putchar('1');
                        lst = 1;
                    }
                    else k += cost;
                }
            }
            puts("");
        }
        else puts("Impossible");
    }
    return 0;
}


1
9 2
????????1
1 7 0 8
1 7 0 6
1 5 0 6
1 5 0 4
1 3 0 4
1 3 0 2
1 1 0 2
1 1 0 0
0 0 0 0
0

answer.code:84:1: error: expected unqualified-id before numeric constant
   84 | 1
      | ^
answer.code: In function ‘int main()’:
answer.code:32:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   32 |         scanf("%s", s + 1);
      |         ~~~~~^~~~~~~~~~~~~