← 返回题目列表

Codeforces · 1706/A

A. 另一个字符串最小化问题

中文机器翻译题面 查看原题

您有一个长度为 $$$n$$$ 的序列 $$$a_1, a_2, \ldots, a_n$$$,由 $$$1$$$ 和 $$$m$$$ 之间的整数组成。您还有一个字符串 $$$s$$$,由 $$$m$$$ 字符组成 B.

您将执行以下 $$$n$$$ 操作。

- 在第 $$$i$$$ ($$$1 \le i \le n$$$) 操作中,将 $$$s$$$ 的第 $$$a_i$$$ 或第 $$$(m + 1 - a_i)$$$ 个字符替换为 A。您可以通过操作多次替换任意位置的字符。

找到这些操作后可以得到的按字典顺序最小的字符串。

按字典顺序,字符串 $$$x$$$ 比相同长度的字符串 $$$y$$$ 小,当且仅当在 $$$x$$$ 和 $$$y$$$ 不同的第一个位置,字符串 $$$x$$$ 在字母表中有一个字母比 $$$y$$$ 中的对应字母更早出现。

输入

第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 2000$$$)。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 50$$$) - 分别是序列 $$$a$$$ 的长度和字符串 $$$s$$$ 的长度。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le m$$$) — 序列 $$$a$$$。

输出

对于每个测试用例,打印一个长度为 $$$m$$$ 的字符串 — 您可以获得的按字典顺序排列的最小字符串。字符串的每个字符必须是大写英文字母A或大写英文字母B。

示例

输入 #1

6
4 5
1 1 3 1
1 5
2
4 1
1 1 1 1
2 4
1 3
2 7
7 5
4 5
5 5 3 5

输出 #1

ABABA
BABBB
A
AABB
ABABBBB
ABABA

注意

在第一个测试用例中,序列 $$$a = [1, 1, 3, 1]$$$。可能的解决方案之一如下。

- 在$$$1$$$-st操作中,可以将$$$s$$$的$$$1$$$-st字符替换为A。之后,$$$s$$$变为ABBBB。
- 在 $$$2$$$-nd 操作中,您可以将 $$$s$$$ 的第 $$$5$$$ 字符替换为 A(因为 $$$m+1-a_2=5$$$)。之后,$$$s$$$ 变为 ABBBA。
- 在$$$3$$$-rd操作中,可以将$$$s$$$中的$$$3$$$-rd字符替换为A。之后,$$$s$$$变为ABABA。
- 在第 $$$4$$$ 操作中,您可以将 $$$s$$$ 的第 $$$1$$$-st 字符替换为 A。之后,$$$s$$$ 仍然等于 ABABA。

在第二个测试用例中,您将仅执行一项操作。将$$$s$$$中的第$$$2$$$个字符或第$$$4$$$个字符替换为A即可。运算后可得到字符串BABBB和BBBAB。字符串 BABBB 是这些字符串中按字典顺序最小的字符串。

在第三个测试用例中,您可以获得的唯一字符串是 A。

在第四个测试用例中,可以将$$$s$$$中的$$$1$$$-st和$$$2$$$-nd字符替换为A,得到AABB。

在第五个测试用例中,可以将$$$s$$$中的$$$1$$$-st和$$$3$$$-rd字符替换为A,得到ABABBBB。