// MagicDark
#include <bits/stdc++.h>
// #define mid ((l + r) >> 1)
// #define lc num << 1
// #define rc lc | 1
// #define li lc, l, mid
// #define ri rc, mid + 1, r
// #define debug cerr << "\33[32m[" << __LINE__ << "]\33[m "
#define all(x) x.begin(), x.end()
#define SZ(x) ((int) x.size() - 1)
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); ++i)
#define DF(i, x, y) for (int i = (x); i >= (y); --i)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> T& chkmax(T& x, T y) {return x = max(x, y);}
template <typename T> T& chkmin(T& x, T y) {return x = min(x, y);}
template <typename T> T& read(T& x) {
    x = 0; int f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = - 1;
    for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
    return x *= f;
}
// mt19937_64 mrand(20070124);
mt19937_64 mrand(20071211);
ll rnd(ll l, ll r) {
    return mrand() % (r - l + 1) + l;
}
const int N = 2e4 + 1010, INF = 1e9 + 10, T = 21, K = T + 5;
const int MOD = 1e9 + 7, inv2 = (MOD + 1) >> 1;
int n, k, a[N], lim[N][K], pw[N * 2], ipw[N * 2], ts[N], pos[N];
int tl[N][K], tr[N][K], wt[N][K];
int qq(int x) {
    return x < 0 ? ipw[- x] : pw[x];
}
int qw(int l, int r) {
    if (r - l + 1 <= T) return wt[r][r - l + 1];
    // int w = 0;
    // F(i, l, r) w = (w + a[i]) / 2;
    // if (w != wt[T][r] + (l <= pos[r])) {
    //     debug << l << " " << r << endl;
    //     debug << w << " " << wt[T][r] << " " << (l <= pos[r]) << endl;
    // }
    // assert(w == wt[T][r] + (l <= pos[r]));
    return wt[r][T] + (l <= pos[r]); 
}
int calc(int a, int b, int c, int t) {
    int d = c - t;
    if (d <= a) {
        return (ll) (ts[b] - ts[a - 1] + MOD) * qq(- a + (a - d)) % MOD;
    }
    // debug << d << endl;
    if (d > b) {
        int delta = d - b - 1;
        if (delta > 30) return 0;
        // int val = wt[min(T, b - a + 1)][b];
        return qw(a, b) >> delta;
    }
    int val = ((ll) (ts[b] - ts[d - 1] + MOD) * qq(- d) + qw(a, d - 1)) % MOD;
    return val;
}
// int cw(int a, int b, int c, int t) {
//     int d = c - t;
//     if (d <= a) {
//         debug << "A\n";
//         return (ll) (ts[b] - ts[a - 1] + MOD) * qq(- a + (a - d)) % MOD;
//     }
//     // debug << d << endl;
//     if (d >= b) {
//         // debug << "B\n";
//         int delta = d - b;
//         if (delta > 30) return 0;
//         // int val = wt[min(T, b - a + 1)][b];
//         return wt[min(T, b - a + 1)][b] >> delta;
//     }
//     // debug << a << " " << d << " " << b << " " << wt[min(T, (d - 1) - a + 1)][d - 1] / 2 << endl;
//     int w = 0;
//     F(i, a, d - 1) {
//         w = (w + ::a[i]) / 2;
//     }
//     // debug << w << endl;
//     // debug << "C\n";
//     int val = ((ll) (ts[b] - ts[d - 1] + MOD) * qq(- d) + (wt[min(T, (d - 1) - a + 1)][d - 1] / 2)) % MOD;
//     return val;
// }
int cc(int a, int b, int c, int t) {
    int x1 = calc(a, b, c, t), x2 = calc(a, b, c, t - 1);
    int val = (x1 - x2 * 2 + MOD * 2ll) % MOD;
    // if (val != 0 && val != 1) {
    //     // cw(a, b, c, t), cw(a, b, c, t - 1);
    //     debug << a << " " << b << " " << c << " " << t << ": " << val << " " << x1 << " " << x2 << endl;
    // }
    // assert(val == 0 || val == 1);
    return val;
}
// int info[N << 2];
// void modify(int num, int l, int r, int x, int y) {
//     if (l == r) {
//         info[num] = y;
//         return;
//     }
//     if (mid)
// }
struct szsz {
    int t[N];
    void init() {
        F(i, 1, n + 1) t[i] = INF;
    }
    void mdf(int x, int y) {
        x++;
        for (; x; x ^= x & - x) chkmin(t[x], y);
    }
    int query(int x) {
        x++;
        // if (x == 0) return - 1;
        int ans = INF;
        for (; x <= n; x += x & - x) chkmin(ans, t[x]);
        return ans;
    }
} ds;
int dp[N];//, ans[N];
bool ff[N][K];
// void print() {
//     F(i, 1, n) {
//         F(j, 1, min(i, T)) {
//             // if (tl[i][j] <= tr[i][j]) 
//             debug << i - j + 1 << " " << i << ' ' << tl[i][j] << " " << tr[i][j] << endl;
//         }
//     }
// }
void zhk() {
    read(n), read(k);
    F(i, 1, n) read(a[i]);
    // F(i, n + 1, n + T) a[i] = 0;
    pw[0] = ipw[0] = 1;
    F(i, 1, n * 2) {
        pw[i] = 2 * pw[i - 1] % MOD;
        ipw[i] = (ll) inv2 * ipw[i - 1] % MOD;
    }
    F(i, 1, n) {
        ts[i] = (ts[i - 1] + (ll) pw[i] * a[i]) % MOD;
    }
    F(i, 1, n) {
        F(j, 1, min(i, T)) {
            tl[i][j] = 1;
            tr[i][j] = i - j + 1;
            // lim[i][j] = i - j + 1;
            int cur = 0;
            DF(k, j, 1) {
                cur = (cur + a[i - k + 1]) / 2;
            }
            wt[i][j] = cur;
        }
        if (i > T) {
            ll v = wt[i][T] + 1;
            DF(j, i, i - T + 1) {
                v = v * 2 - a[j];
                if (v > INF) break;
            }
            pos[i] = 0;
            if (v <= INF) {
                int pp = i - T;
                F(j, 1, min(T, pp))
                    if (wt[pp][j] >= v) {
                        pos[i] = pp - j + 1;
                        break;
                    }
                if (!pos[i]) {
                    if (wt[pp][min(T, pp)] + 1 == v) pos[i] = pos[pp];
                }
            }
            // if (pos[i]) {
            //     debug << i << " " << pos[i] << endl;
            // }
        }
        // F(j, max(1, i - T), i - 1) {
        //     cur = (cur + a[j]) / 2;
        // }
        // wt[i] = cur;
    }
    // debug << calc(6, 10, 10, 1) << endl;
    // exit(0);
    int lsta = - 1, lstb, lstc;
    // int wcnt = 0;
    // print();
    while (true) {
        // wcnt++;
        // if (++wcnt > 10) assert(0);
        ll s = 0;
        F(i, 1, n) {
            F(j, 1, min(i, T)) if (tl[i][j] <= tr[i][j]) {
                s += tr[i][j] - tl[i][j] + 1;
            }
        }
        // debug << s << endl;
        if (!s) break;
        ll pos = rnd(1, s);
        auto solve = [&] (int a, int b, int c) {
            ds.init();
            ds.mdf(0, - 1);
            F(i, 1, n) {
                dp[i] = INF;
                F(j, 1, min(i, T)) {
                    ff[i][j] = false;
                    int t = i - j + 1;
                    // int tl = - T, tr = n + 1;
                    // while (tl + 1 < tr) {
                    //     int mid = (tl + tr) >> 1;
                    //     if (calc(a, b, c, mid) == calc(1, i - j + 1, i, mid)) tl = mid;
                    //     else tr = mid;
                    // }
                    // int t1 = calc(a, b, c, tl), t2 = calc(1, i - j + 1, i, tl);
                    // assert(t1 != t2);
                    // int lim;
                    // if (!t2) {
                    //     lim = 1;
                    // } else {
                    //     int d = i - tl;
                    //     lim = max(1, );
                    // }
                    int wl = tl[i][j] - 1, wr = tr[i][j] + 1;
                    int kl = - T, kr = - T;
                    while (wl + 1 < wr) {
                        int wmid = (wl + wr) >> 1;
                        int pl = min(kl, kr);//, pr = n + 1;
                        int p = 0;
                        while (true) {
                            int pmid = pl + (1 << p);
                            if (pmid > n || calc(a, b, c, pmid) != calc(wmid, t, i, pmid)) break;
                            pl = pmid;
                            p++;
                        }
                        while (p) {
                            p--;
                            int pmid = pl + (1 << p);
                            if (pmid <= n && calc(a, b, c, pmid) == calc(wmid, t, i, pmid)) pl = pmid;
                        }
                        // while (pl + 1 < pr) {
                        //     int pmid = (pl + pr) >> 1;
                        //     if (calc(a, b, c, pmid) == calc(wmid, t, i, pmid)) pl = pmid;
                        //     else pr = pmid;
                        // }
                        // if (t == 2 && i == 3) {
                        //     debug << a << " " << b << " " << c << endl;
                        //     debug << wmid << " " << t << ' ' << i << endl;
                        //     debug << wmid << ' ' << pr << endl;
                        // }
                        if (pl == n) {
                            ff[i][j] = true;
                            wr = wmid;
                            break;
                        } else {
                            // int t1 = cc(a, b, c, pr), t2 = cc(wmid, t, i, pr);
                            // debug << t1 << ' ' << t2 << endl;
                            // assert(t1 != t2);
                            if (!cc(wmid, t, i, pl + 1)) {
                                kr = pl;
                                wr = wmid;
                            } else {
                                kl = pl;
                                wl = wmid;
                            }
                        }
                        // int lim;
                        // if (!t2) {
                        //     lim = 1;
                        // } else {
                        //     int d = i - tl;
                        //     lim = max(1, );
                        // }
                    }
                    // if (t == 2 && i == 3) {
                    //     debug << wr << endl;
                    // }
                    lim[i][j] = wr;
                    // if (a == 1 && b == 1 && c == 1) {
                    //     debug << t << " " << i << " " << wr << endl;
                    // }
                    if (wr != t + 1) {
                        int val = ds.query(wr - 1) + i - (t + 1);
                        if (val < dp[t]) {
                            ds.mdf(t, dp[t] = val);
                        }
                    }
                }
                // if (a == 1 && b == 1 && c == 1) {
                //     debug << i << " " << dp[i] + (i + 1) << endl;
                // }
            }
            // debug << c - b + 1 << ' ' << c << endl;
            // debug << tl[c - b + 1][c] << " " << tr[c - b + 1][c] << endl;
            // debug << dp[n] + (n + 1) << endl;
            if (dp[n] + (n + 1) <= k) {
                // debug << "!\n";
                lsta = a, lstb = b, lstc = c;
                F(i, 1, n) {
                    F(j, 1, min(i, T)) {
                        tl[i][j] = lim[i][j];
                        if (ff[i][j]) tl[i][j]++;
                    }
                }
            } else {
                F(i, 1, n) {
                    F(j, 1, min(i, T)) {
                        tr[i][j] = lim[i][j] - 1;
                        // if (ff[i][j]) tr[i][j]--;
                    }
                }
            }
            // print();
            // debug << "# " << a << " " << b << " " << c << " " << lim[c - b + 1][c] << '\n';
            // debug << tl[c - b + 1][c] << " " << tr[c - b + 1][c] << endl;
        };
        auto work = [&] () {
            F(i, 1, n) {
                F(j, 1, min(i, T)) if (tl[i][j] <= tr[i][j]) {
                    int len = tr[i][j] - tl[i][j] + 1;
                    if (pos <= len) {
                        // debug << tl[i][j] << " " << tr[i][j] << " " << len << " " << pos << endl;
                        solve(tl[i][j] + pos - 1, i - j + 1, i);
                        return;
                    } else pos -= len;
                }
            }
            // assert(false);
        };
        work();
        // exit(0);
    }
    // cerr << wcnt << endl;
    // assert(lsta != - 1);
    bool flag = false;
    F(i, - T, n) {
        int ans = cc(lsta, lstb, lstc, i);
        if (!flag) {
            if (ans) flag = true;
        }
        if (flag) cout << ans;
    }
    cout << '\n';
}
signed main() {
    int _; read(_);
    while (_--) zhk();
    return 0;
}
/* why
*/