区间 dp。$dp_{i,j}$ 表示凑出区间 $[i, j]$ 的最小代价。考虑枚举当前区间 $[i, j]$ 与 $k$，找到一个最大的 $p$，使得 $[i, j]$ 在区间 $[p, j]$ 中不重叠地出现了 $k$ 次。则有转移：

$$dp_{p,j} \leftarrow \min(dp_{p,j}, dp_{i,j} + B + k \times C + (j - p + 1 - k \times len) \times A)$$

以及最基本的：

$$dp_{i,j} \leftarrow \min(dp_{i+1,j} + A, dp_{i,j-1} + A, dp_{i,j})$$

这部分复杂度为 $O(\sum \frac{n}{j-i+1}) = O(n^2 \ln n)$。

现在就要考虑怎么找这个 $k$ 对应的 $p$。考虑 dp 求出 $S$ 每两个后缀的 $\mathrm{lcp}$，然后处理出对于一对 $(i, k)$ 的最大的 $j < i$，使得 $\mathrm{lcp}(S[i: n], S[j: n]) \geq k$。这个东西可以先记录 $= k$ 的情况，然后求后缀最大值。

时间复杂度 $O(n^2)$。

将 $0/1$ 理解为 $\pm 1$，做一个前缀和。

构造 $\{t_{i}\}=10101\cdots$。

此时，将两者"乱序归并"后，其对 $\{s_{i}\}$ 前缀和的影响不大。

记 $a_{i}$ 为 $A$ 二进制下第 $i$ 位，$\forall i\in [1,60]$ 依次在 $\{s_{i}\}$ 末尾加入 $2+[a_{i}\ne a_{i-1}]$ 个 $a_{i}$（定义 $a_{0}=1$）

乱序合并后，维护 $s$ 表示 $\{u_{i}\}$ 的前缀和，每当 $|s|\ge 2$ 则得到下一位（根据 $s$ 的符号）并清空 $s=0$，这样就能忽略乱序归并 $\{t_i\}$ 带来的对前缀和的影响了。

事实上，上述做法本质上即能够确定满足每一个极长 $0/1$ 段的长度为 $\ge 3$ 的奇数的 $\{s_{i}\}$（第一段不一定是奇数，因为 $a_0=1$）

考虑进行映射，给每个符合条件的 $\{s_i\}$ 一个编号。

那么 Anna 仅需将需要存储的数作为编号找到对应的 $\{s_i\}$，然后传给 Bruno，Bruno 再反向查回编号即可得到答案。

注意到 Bruno 无法确定 $\{s_i\}$ 的长度，不妨在 $\{s_i\}$ 末尾插入一部分以 $01$ 为循环节的串。

最后还有一个优化：在 $\{s_{i}\}$ 开头增加一个 $A$ 的二进制最后一位，并在 $A$ 的最后一位和 $\{t_{i}\}$ 的第一位（$1$）不同的前提下将所有 $\{s_{i}\}$ 和 $\{t_{i}\}$ 中的 $01$ 翻转，此时，$A$ 中的最后一位可以仅用 $1$ 个 bit 确定（此时 $u_0$ 必定等于 $A$ 的二进制最后一位），因此可以少用一个 $0/1$ 连续段。

DP 计数得上述形式且长度 $\le 140$ 的 $\{s_{i}\}$ 个数 $\ge 10^{18}$，可以通过本题。

我们可以把每个串看成一个集合，所以总共有 $m$ 个集合，对于每个团子，我们尝试将其插入某个集合中。插入时需要维护以下性质：

一：每个集合内的每个团子的颜色互不相同。

二：同一种颜色的团子是按串串的编号从左到右放到每个串串中的。

所以现在问题变为了如何检验这个颜色的团子放在哪里。

而我们似乎只能用 Query(x[]) 函数来检验，但是我们总共只能调用 $50000$ 次 Query(x[]) 函数。而团子的总数最多有 $m \times n$ 即 $10000$ 个。所以我们需要在最多调用 $5$ 次 Query(x[]) 函数的情况下来求出这个团子放在哪。

我们根据这些想到可以二分，因为根据性质二，这种颜色的团子一定是前面一段串串有，后面的串串全部都没有的，所以可以通过二分的方式来查找。而二分要调用大约 $\log_2 25$ 次 Query(x[]) 函数，而 $4 \leq \log_2 25 \leq 5$，刚好小于等于 $5$，所以我们接下来就要考虑怎么二分了。

我们先假设前几个串串上已经有了一些团子，就像这样：

那么对于下一个这种颜色的团子，如果我们放在这两个已经有这种颜色的串上，就像这样：

由于这种颜色的团子的个数等于总的串串数，所以如果我们放在这两个已经有这种颜色的串上的话，所有剩下的团子就没有办法组成剩下串串的个数个一流团子串。（建议自己在纸上画一下）欸，这不就可以用到 Query(x[]) 函数了吗！

我们设当前的团子放在第 $mid$ 个串上，那么如果所有没有处理的团子和第 $mid + 1$ 到第 $m$ 个串上的所有团子加起来能做出至少 $m - mid$ 个一流团子串的话，这个团子就可以放在第 $mid$ 个串上。就像这样（能放的情况）：

我们钦定第 $i$ 个团子可以放在第 $j$ 个串上，那么它一定能放在第 $k\in[1,j]$ 个串上。同时，如果我们现在放到了 $j$ 上，那么对于第 $[i+1,nm]$ 个的团子，这种放到 $j$ 上的方案必定不劣于放到 $k$ 上，因为这样 $[mid + 1, m]$ 一定能做出更多团子。

我们就用这个进行二分，如果能做出至少 $m - mid$ 个一流团子串，我们就把 $r$ 赋值为 $mid - 1$，同时用 $ans$ 记录下 $mid$，否则就把 $l$ 赋值为 $mid + 1$，二分的边界条件为 $l \leq r$。二分完后就把这个团子放入第 $ans$ 个串串中。把每个团子都这样处理后这道题就做完了。