← 返回题目列表

Codeforces · 1986/C

C. 更新查询

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

让我们考虑以下简单问题。给定一个长度为 $$$n$$$ 的字符串 $$$s$$$,由小写拉丁字母组成,以及一个长度为 $$$m$$$ 的索引 $$$ind$$$ 数组 ($$$1 \leq ind_i \leq n$$$) 和一个长度为 $$$m$$$ 的字符串 $$$c$$$,由小写拉丁字母组成。然后,按顺序执行更新操作,即在第 $$$i$$$ 操作期间,设置 $$$s_{ind_i} = c_i$$$。请注意,您执行从第一个到最后一个的所有 $$$m$$$ 操作。

当然,如果更改数组 $$$ind$$$ 中的索引顺序和/或字符串 $$$c$$$ 中的字母顺序,您可以获得不同的结果。如果您可以根据需要重新排列数组 $$$ind$$$ 中的索引和字符串 $$$c$$$ 中的字母,请找到在 $$$m$$$ 更新操作后可以获得的按字典顺序最小的字符串 $$$s$$$。

当且仅当满足以下条件之一时,字符串 $$$a$$$ 按字典顺序小于字符串 $$$b$$$:

- $$$a$$$ 是 $$$b$$$ 的前缀,但 $$$a \neq b$$$;
- 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,字符串 $$$a$$$ 中的符号在字母表中早于字符串 $$$b$$$ 中的相应符号。

输入

每个测试都包含多组输入数据。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 输入数据的组数。然后是他们的描述。

每组输入数据的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n, m \leq 10^5$$$) — 字符串 $$$s$$$ 的长度和更新次数。

每组输入数据的第二行包含一个长度为$$$n$$$的字符串$$$s$$$,由小写拉丁字母组成。

每组输入数据的第三行包含 $$$m$$$ 整数 $$$ind_1, ind_2, \ldots, ind_m$$$ ($$$1 \leq ind_i \leq n$$$) — 索引 $$$ind$$$ 数组。

每组输入数据的第四行包含一个长度为$$$m$$$的字符串$$$c$$$,由小写拉丁字母组成。

保证所有输入数据集的 $$$n$$$ 之和不超过 $$$2 \cdot 10^5$$$。同样,所有输入数据集的 $$$m$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每组输入数据,输出字典顺序最小的字符串 $$$s$$$,该字符串可以通过重新排列数组 $$$ind$$$ 中的索引和字符串 $$$c$$$ 中的字母来获得。

示例

输入 #1

4
1 2
a
1 1
cb
4 4
meow
1 2 1 4
zcwz
7 4
abacaba
1 3 5 7
damn
7 10
traktor
7 6 5 4 3 2 1 6 4 2
codeforces

输出 #1

b
cwoz
abdcmbn
ccdeefo

注意

在第一组输入数据中,您可以保留数组 $$$ind$$$ 和字符串 $$$c$$$ 不变,并按该顺序执行所有操作。

在第二组输入数据中,可以设置数组 $$$ind = [1, 1, 4, 2]$$$ 和 $$$c =$$$ "zczw"。那么字符串 $$$s$$$ 将发生如下变化:$$$meow \rightarrow zeow \rightarrow ceow \rightarrow ceoz \rightarrow cwoz$$$。

在第三组输入数据中,您可以保留数组 $$$ind$$$ 不变,并设置 $$$c = $$$ "admn"。那么字符串 $$$s$$$ 将发生如下变化:$$$abacaba \rightarrow abacaba \rightarrow abdcaba \rightarrow abdcmba \rightarrow abdcmbn$$$。