# 克隆缸

- 参考时间限制：0.5 秒（参考环境：[评测环境与性能](../../../docs/评测环境与性能.md)；仅供预估）
- 实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整；若平台仅支持更粗的粒度，再向上取整到平台可设置值。
- 内存限制：8 MB

## 背景故事

尤里准备测试克隆缸：把一段形如 $AcA$ 的 DNA 从中间分开，复制其中一侧，再与另一侧比较。实验室收到的 DNA 尚未满足要求，而且每份样本规定了必须恰好改变的核苷酸数量。请给出字典序最小的改造方案。

## 形式化问题描述

给定奇数长度 $n$ 的字符串 $s$ ，字符集为 `0` 、`1` 、`2` 、`3` ，以及整数 $m$ .令 $h=(n-1)/2$ .请构造同长度字符串 $t$ ，满足：

1. $t_i=t_{h+1+i}$ 对所有 $1\le i\le h$ 成立，即前半段与后半段按从左到右的顺序相同。
2. 恰好有 $m$ 个位置满足 $t_i\ne s_i$ ，中间位置也计入。

中间字符 $t_{h+1}$ 可任意选择，不要求与其他字符相等。比较的是最终字符与初始字符，不统计编辑动作的次数。

![长度为7的字符串分为左半段、中心字符和右半段；0123012改为0023002，仅第2和第6个位置改变](assets/aligned-halves.svg)

图 1：输入串为 `0123012` 、$m=2$ 时，可以得到 `0023002` .对应配对为位置 $1$ 与 $5$ 、$2$ 与 $6$ 、$3$ 与 $7$ ；这不是从两端向中间的镜像配对。粗框标记改变的位置。

在所有合法字符串中输出字典序最小者，字符顺序为 `0` < `1` < `2` < `3` .不存在合法字符串时输出 `failed` .每个询问独立。

## 输入格式

第一行一个整数 $q$ .接下来 $q$ 行，每行依次给出 $n,m,s$ .

## 输出格式

输出 $q$ 行，每行一个合法字符串，或 `failed` .

## 样例 1

### 输入

```text
2
3 3 000
3 0 100
```

### 输出

```text
111
failed
```

### 解释

第一个询问必须改变全部位置，最小可用字符为 `1` .第二个询问不允许修改，但两个半段已经不同。

## 样例 2

### 输入

```text
4
1 0 3
1 1 3
7 2 0123012
3 1 000
```

### 输出

```text
3
0
0023002
010
```

### 解释

长度为一时只有中心字符。最后一个询问只改变中心，能够保留最小的左半段 `0` .

## 数据范围与保证

- $1\le q\le1000000$ ，每个 $n$ 为正奇数，所有询问的 $\sum n\le1000000$ .
- $0\le m\le n$ ，$s$ 长度恰为 $n$ ，且仅含 `0` 到 `3` .

### 数据分组

| 分值比例 | 额外条件 |
| --- | --- |
| 100% | 无额外条件 |