CF1986C.Update Queries

让我们考虑如下的简单问题。给定一个长度为 $n$ 的字符串 $s$，由小写拉丁字母组成，以及一个长度为 $m$ 的下标数组 $ind$（$1 \leq ind_i \leq n$），和一个长度为 $m$ 的字符串 $c$，由小写拉丁字母组成。然后，依次进行 $m$ 次更新操作，即在第 $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 \times 10^5$，所有 $m$ 的总和也不超过 $2 \times 10^5$。

对于每组测试数据，输出经过任意重排 $ind$ 和 $c$ 后，能够得到的字典序最小的字符串 $s$。

在第一组测试数据中，你可以保持数组 $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$。

由 ChatGPT 4.1 翻译