本文主要介绍不依赖于 bitset 的 $\mathcal{O} (\sum n k \sqrt k)$ 做法。

不妨研究一下“摩卡串”对于“字典序小于 $s$ 的子串”的限制等价于什么。考虑 $s = \texttt{11010}$，列出字典序比这个字符串小的所有字符串，不难发现它们恰能被如下正则表达式之一匹配：

1
11
110
1101

0[01]*
10[01]*
1100[01]*

不难发现，上面的字符串分为两种：

• 第一种是 $s$ 的所有真前缀；
• 第二种是取所有 $s$ 的前缀，满足最后一个位置是 $\texttt{1}$，随后将其换成 $\texttt{0}$，并允许在后面继续添加任意 01 字符串。

因此，考虑不断向字符串 $t$ 的末尾追加字符的过程，在追加一个新字符时，根据增量思想应该只考虑 $t$ 的所有新的后缀。此时：

• 如果某个新的后缀与第一种字符串匹配，则自然会多一个字典序小于 $s$ 的子串；
• 如果某个新的后缀与第二种字符串匹配，则除了在这个位置产生贡献之外，它也会在之后每次追加字符时产生贡献。

接下来分别研究上述两种情况的性质：

• $t$ 的后缀等于 $s$ 的某个前缀。回顾 KMP 相关的内容，在我们尝试匹配字符串时，在中途维护的匹配位置恰好就是满足文本串中被扫描部分的后缀与关键词串的前缀相同的最大长度，而其他满足上述性质的长度都可以通过不断跳 next 数组得到。因此在实际维护时，需要先对字符串 $s$ 跑一次 KMP，并计算“next 树”上每个位置的深度（这里只计算真前缀，因此需要额外讨论位置 $n$ 的深度），在后续状态转移时只需要维护匹配位置，并将深度作为增量累加即可。
• $t$ 的后缀等于 $s$ 的某个前缀将末尾的 $\texttt{1}$ 改为 $\texttt{0}$ 的产物。不难发现追加的字符应当为 $\texttt{0}$。此时假设 $t$ 在本次追加前的匹配位置为 $p$，则从 $p$ 开始不断跳 next，若跳到的其中一个位置 $q$ 满足 $s_{q + 1} = \texttt{1}$，则追加之后字符串 $t$ 中长度为 $q + 1$ 的后缀就满足第二种情况。

因此，匹配过程中的状态为：

• $t$ 当前部分的后缀和 $s$ 的前缀匹配的最大长度，也就是 KMP 的匹配位置；
• 第二种情况总共触发了多少次；
• $t$ 当前部分中字典序小于 $s$ 的子串个数
• $t$ 当前部分是否包含 $s$ 作为子串。

使用 BFS 搜索从 $(0, 0, 0, 0)$ 状态到达 $(\circ, \circ, k, 1)$ 状态的最短路即可。此时的时间复杂度为 $\mathcal{O} (\sum n k^2)$。

接下来需要注意到：在第二种情况触发时，实际上对应的是一次失配，而这次失配之前还包含了多次匹配，也就是第一种情况触发时的情况。可以证明，如果第二种情况触发了 $c$ 次，则字典序小于 $s$ 的子串个数不小于 $\frac{c (c + 1)} 2$。因此，状态的第二维实际上不会超过 $\mathcal{O}(\sqrt k)$。

在上述讨论之后，该做法的时间复杂度降低至 $\mathcal{O} (\sum n k \sqrt k)$，可以通过。

::::info[代码]

// https://qoj.ac/submission/2105504

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>

using namespace std;

int t, n, k;
char s[210];

int nxt[210];
int mtch[210][2], accu[210][2];
int dep[210];

const int MAX_P = 200;
const int MAX_C = 80;

/*
  状态：
    p - t 的后缀匹配 s 的前缀的最长长度
    c - t 加 0 时对应的失配总数
  cnt - 字典序比 s 小的子串数量
   ok - t 是否存在 s 作为子串
*/

struct Transition {
  short ch;
  short lp, lc, lk, lok;
};

Transition dp[MAX_P + 1][MAX_C + 1][3010][2];
bool vis[MAX_P + 1][MAX_C + 1][3010][2];

queue<tuple<short, short, short, short>> que;

int main() {
  int _;
  scanf("%d%d", &_, &t);
  while (t --) {
    scanf("%d %d %s", &n, &k, s + 1);

    nxt[1] = 0;
    dep[1] = (n != 1);
    for (int i = 2, j = 0; i <= n; i ++) {
      while (j != 0 && s[i] != s[j + 1])
        j = nxt[j];
      if (s[i] == s[j + 1])
        ++ j;
      nxt[i] = j;
      dep[i] = dep[j] + (i != n);
    }

    for (int i = 0; i <= n; i ++) {
      for (int j: {0, 1}) {
        int pos = i, cnt = 0;
        while (pos != 0 && s[pos + 1] != j + '0')
          pos = nxt[pos];
        if (s[pos + 1] == j + '0')
          ++ pos;
        mtch[i][j] = pos;

        pos = i;
        while (pos != 0)
          cnt += s[pos + 1] == '1', pos = nxt[pos];
        cnt += s[1] == '1';
        accu[i][j] = cnt;
      }
    }

    memset(vis, 0, sizeof vis);
    dp[0][0][0][0] = {0, 0, 0, 0, 0};
    vis[0][0][0][0] = true;

    while (!que.empty()) que.pop();
    que.push({0, 0, 0, 0});
    
    bool flg = false;
    tuple<int, int, int, int> st;
    while (!que.empty()) {
      auto [p, c, lk, ok] = que.front();
      que.pop();
      if (ok && (lk == k)) {
        flg = true;
        st = {p, c, lk, ok};
        break;
      }
      for (int ch : {0, 1}) {
        int np = mtch[p][ch];
        int nc = c + (ch == 0) * accu[p][ch];
        int nk = lk + nc + dep[np];
        int nok = ok || (np == n);
        if (nk <= k) {
          if (!vis[np][nc][nk][nok]) {
            vis[np][nc][nk][nok] = true;
            dp[np][nc][nk][nok] = {
              ch, p, c, lk, ok
            };
            que.push({np, nc, nk, nok});
          }
        }
      }
    }

    if (!flg) {
      puts("Impossible");
      continue;
    }

    auto [p, c, lk, ok] = st;
    string str = "";
    while (p != 0 || c != 0 || lk != 0 || ok != 0) {
      auto [ch, np, nc, nlk, nok] = dp[p][c][lk][ok];
      str = char('0' + ch) + str;
      p = np; c = nc; lk = nlk; ok = nok;
    }

    puts(str.c_str());
  }
  return 0;
}

::::