#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 3e4 + 5, B = 20;
const int mod[3] = {998244353, (int)1e9 + 7, (int)1e9 + 9}, inf = (int)1e9 + 5;
int pw[3][N];
int sum[3][N];
int val[N][35], mx[N], pos[N], a[N], n;
int qry(int l, int r)
{
    if(r - l <= B)
        return val[r][r - l];
    return mx[r] - (l > pos[r]);
}
struct node
{
    int l, r, k;
    node(int l0 = 0, int r0 = 0, int k0 = 0)
    {
        l = l0;
        r = r0;
        k = k0;
    }
    int qval()
    {
        return qry(l, r) >> k;
    }
    int qbit(int x)
    {
        x -= k;
        if(x < 0)
            return (qry(l, r) >> (-x)) & 1;
        if(x > r - l)
            return 0;
        return qry(l, r - x) & 1;
    }
    int hs(int x)
    {
        x -= k;
        if(x < 0)
        {
            int v = qry(l, r) >> (-x);
            return {v, v, v};
        }
        if(x > r - l)
            return (sum[0][l] + (ll)(mod[0] - pw[0][r - l + 1]) * sum[0][r + 1]) % mod[0] * pw[0][x - r + l] % mod[0];
        return (qry(l, r - x) + 2 * (sum[0][r - x + 1] + (ll)(mod[0] - pw[0][x]) * sum[0][r + 1])) % mod[0];
    }
};
bool chk(node A, node B) // A < B
{
    int lim = n + 30;
    if(A.hs(lim) == B.hs(lim))
        return make_pair(make_pair(A.l, A.r), A.k) < make_pair(make_pair(B.l, B.r), B.k);
    // printf("A\n");
    if(A.qval() != B.qval())
        return A.qval() < B.qval();
    // printf("B\n");
    int l, r, mid;
    l = 1;
    r = lim;
    while(l <= r)
    {
        mid = (l + r) >> 1;
        // printf("PP%d %d %d\n", mid, A.hs(mid)[0], B.hs(mid)[0]);
        if(A.hs(mid) == B.hs(mid))
            l = mid + 1;
        else
            r = mid - 1;
    }
    // printf("OO%d %d %d\n", l, A.qbit(l), B.qbit(l));
    return A.qbit(l) < B.qbit(l);
}
ll dp[N][35];
int lp[N][35], L[N][35], R[N][35];
ll mnv[21][N];
node ans;
vector<int> out;

int main()
{
    mt19937_64 rng(123823);
    int T, k, i, j, p, fl, l, r, mid;
    ll tmp, tot, x;
    node qwq;
    n = 3e4;
    for(j = 0; j < 3; j++)
    {
        pw[j][0] = 1;
        for(i = 1; i <= n; i++)
            pw[j][i] = 2ll * pw[j][i - 1] % mod[j];
    }
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &n, &k);
        for(i = 1; i <= n; i++)
            scanf("%d", a + i);
        for(j = 0; j < 3; j++)
        {
            sum[j][n + 1] = 0;
            for(i = n; i >= 1; i--)
                sum[j][i] = (2ll * sum[j][i + 1] + a[i]) % mod[j];
        }
        for(i = 1; i <= n; i++)
        {
            tmp = 0;
            memset(val[i], 0, sizeof(val[i]));
            mx[i] = pos[i] = 0;
            for(j = i; j >= max(i - B, 1); j--)
            {
                tmp = 2 * tmp + a[j];
                val[i][i - j] = (tmp >> (i - j));
                if(val[i][i - j] > mx[i])
                {
                    mx[i] = val[i][i - j];
                    pos[i] = j;
                }
            }
            if(mx[i - 1] / 2 + a[i] > mx[i])
            {
                mx[i] = mx[i - 1] / 2 + a[i];
                pos[i] = pos[i - 1];
            }
        }
        // for(i = 1; i <= n; i++)
        //     for(j = i; j <= n; j++)
        //         printf("??%d %d %d\n", i, j, qry(i, j));
        ans = node(n, n, -1);
        tot = 0;
        for(i = 1; i <= n; i++)
            for(j = 0; j <= B; j++)
            {
                L[i][j] = 1;
                R[i][j] = i;
                tot += R[i][j] - L[i][j] + 1;
            }
        // printf("#%d\n", chk(node(1, 1, 1), node(6, 9, 0)));
        // return 0;
        while(tot)
        {
            x = rng() % tot + 1;
            fl = 0;
            qwq = node(n, n, -1);
            for(i = 1; i <= n; i++)
            {
                for(j = 0; j <= B; j++)
                    if(x <= R[i][j] - L[i][j] + 1)
                    {
                        fl = 1;
                        qwq = node(L[i][j] - 1 + x, i, j);
                        break;
                    }
                    else
                        x -= max(R[i][j] - L[i][j] + 1, 0);
                if(fl)
                    break;
            }
            for(i = 1; i <= n; i++)
                for(j = 0; j <= B; j++)
                    if(i == qwq.r && j == qwq.k)
                        lp[i][j] = qwq.l;
                    else
                    {
                        l = 1;
                        r = i;
                        while(l <= r)
                        {
                            mid = (l + r) >> 1;
                            if(chk(node(mid, i, j), qwq))
                                r = mid - 1;
                            else
                                l = mid + 1;
                        }
                        lp[i][j] = l;
                    }
            // printf("#%lld %d %d %d\n", tot, qwq.l, qwq.r, qwq.k);
            // for(i = 1; i <= n; i++)
            //     for(j = 0; j <= B; j++)
            //         printf("!!%d %d: %d %d %d\n", i, j, L[i][j], R[i][j], lp[i][j]);
            // return 0;
            for(i = 0; i <= B; i++)
                dp[0][i] = 0;
            for(i = 1; i <= n; i++)
            {
                for(j = 0; j <= B; j++)
                {
                    dp[i][j] = (j ? dp[i][j - 1] : inf);
                    if(lp[i][j] >= i - B)
                    {
                        for(p = i; p >= lp[i][j]; p--)
                            dp[i][j] = min(dp[i][j], dp[p - 1][min(j + i - p, B)] + j + i - p);
                        continue;
                    }
                    for(p = i; p >= i - B; p--)
                        dp[i][j] = min(dp[i][j], dp[p - 1][min(j + i - p, B)] + j + i - p);
                    // for(p = i - B - 1; p >= lp[i][j]; p--)
                    //     dp[i][j] = min(dp[i][j], dp[p - 1][B] + j + i - p);
                    int Lp = lp[i][j], Rp = i - B - 1;
                    int oo = __lg(Rp - Lp + 1);
                    dp[i][j] = min(dp[i][j], min(mnv[oo][Rp], mnv[oo][Lp + (1 << oo) - 1]) + j + i);
                }
                mnv[0][i] = dp[i - 1][B] - i;
                for(j = 1; j <= __lg(i); j++)
                    mnv[j][i] = min(mnv[j - 1][i], mnv[j - 1][i - (1 << (j - 1))]);
            }
            if(dp[n][0] <= k)
            {
                ans = qwq;
                for(i = 1; i <= n; i++)
                    for(j = 0; j <= B; j++)
                        L[i][j] = max(L[i][j], lp[i][j] + (i == qwq.r && j == qwq.k));
            }
            else
                for(i = 1; i <= n; i++)
                    for(j = 0; j <= B; j++)
                        R[i][j] = min(R[i][j], lp[i][j] - 1);
            tot = 0;
            for(i = 1; i <= n; i++)
                for(j = 0; j <= B; j++)
                    tot += max(R[i][j] - L[i][j] + 1, 0);
        }
        // printf("#%d %d %d\n", ans.l, ans.r, ans.k);
        out.clear();
        p = n - ans.k - ans.r + ans.l;
        while(p--)
            out.emplace_back(0);
        tmp = 0;
        for(i = ans.l; i <= ans.r; i++)
        {
            if(i > ans.l)
                out.emplace_back(tmp & 1);
            tmp = tmp / 2 + a[i];
        }
        while(tmp)
        {
            out.emplace_back(tmp & 1);
            tmp /= 2;
        }
        reverse(out.begin(), out.end());
        for(auto o: out)
            printf("%d", o);
        printf("\n");
        // return 0;
    }
    return 0;
}

answer.code: In member function ‘int node::hs(int)’:
answer.code:45:28: error: cannot convert ‘<brace-enclosed initializer list>’ to ‘int’ in return
   45 |             return {v, v, v};
      |                            ^
answer.code: In function ‘int main()’:
answer.code:95:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   95 |     scanf("%d", &T);
      |     ~~~~~^~~~~~~~~~
answer.code:98:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   98 |         scanf("%d%d", &n, &k);
      |         ~~~~~^~~~~~~~~~~~~~~~
answer.code:100:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  100 |             scanf("%d", a + i);
      |             ~~~~~^~~~~~~~~~~~~