克隆缸¶
- 参考时间限制：0.5 秒（参考环境：评测环境与性能；仅供预估）
- 实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整；若平台仅支持更粗的粒度，再向上取整到平台可设置值。
- 内存限制：8 MB
背景故事¶
尤里准备测试克隆缸：把一段形如 \(AcA\) 的 DNA 从中间分开，复制其中一侧，再与另一侧比较。实验室收到的 DNA 尚未满足要求，而且每份样本规定了必须恰好改变的核苷酸数量。请给出字典序最小的改造方案。
形式化问题描述¶
给定奇数长度 \(n\) 的字符串 \(s\) ，字符集为 0 、1 、2 、3 ，以及整数 \(m\) .令 \(h=(n-1)/2\) .请构造同长度字符串 \(t\) ，满足：
- \(t_i=t_{h+1+i}\) 对所有 \(1\le i\le h\) 成立，即前半段与后半段按从左到右的顺序相同。
- 恰好有 \(m\) 个位置满足 \(t_i\ne s_i\) ，中间位置也计入。
中间字符 \(t_{h+1}\) 可任意选择，不要求与其他字符相等。比较的是最终字符与初始字符，不统计编辑动作的次数。
图 1：输入串为 0123012 、\(m=2\) 时，可以得到 0023002 .对应配对为位置 \(1\) 与 \(5\) 、\(2\) 与 \(6\) 、\(3\) 与 \(7\) ；这不是从两端向中间的镜像配对。粗框标记改变的位置。
在所有合法字符串中输出字典序最小者，字符顺序为 0 < 1 < 2 < 3 .不存在合法字符串时输出 failed .每个询问独立。
输入格式¶
第一行一个整数 \(q\) .接下来 \(q\) 行，每行依次给出 \(n,m,s\) .
输出格式¶
输出 \(q\) 行，每行一个合法字符串，或 failed .
样例 1¶
输入¶
2
3 3 000
3 0 100
输出¶
111
failed
解释¶
第一个询问必须改变全部位置，最小可用字符为 1 .第二个询问不允许修改，但两个半段已经不同。
样例 2¶
输入¶
4
1 0 3
1 1 3
7 2 0123012
3 1 000
输出¶
3
0
0023002
010
解释¶
长度为一时只有中心字符。最后一个询问只改变中心，能够保留最小的左半段 0 .
数据范围与保证¶
- \(1\le q\le1000000\) ，每个 \(n\) 为正奇数，所有询问的 \(\sum n\le1000000\) .
- \(0\le m\le n\) ，\(s\) 长度恰为 \(n\) ，且仅含
0到3.
数据分组¶
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |