题解

题目描述

给定两个字符串 $A$ 和 $B$，以及一个转换数组 $X$，需要通过调整 $X$ 和 $B$ 的顺序，使得替换后的字符串 $A'$ 的字典序最小。替换规则为：遍历调整后的 $X$，将 $B$ 中的字符依次替换到 $A$ 的对应位置，最后一次替换的字符决定该位置的最终值。

思路分析

这道题的核心是通过调整转换数组 $X$ 和字符串 $B$ 的顺序，使得替换后的字符串 $A'$ 的字典序最小。具体步骤是：首先统计每个位置在 $X$ 中的出现次数，收集所有被替换的位置并按升序排列；然后将字符串 $B$ 的字符按升序排序，并将排序后的字符依次分配给被替换的位置，确保前面的位置使用更小的字符，从而保证最终字符串的字典序最小。

题目内容

多多最新在研究一种神奇的字符串替换，该字符串可以通过一种方式进行替换，替换后可以得到另一种学符串。 假设给定两个由小写字母组成的字符串$A$和$B$，对应的字符串长度分别为$n$和$m$;另外，还有一个由$m$个元素组成的转换数组$X$={$index_1,index_2,....,index_m$}，数组的元素记录了字符串A中某些元素的下标(字符串中元素的下标从$1$到$n$)，这些元素可能是重复的，也就是$X$数组中任意元素满足:$1<= index_i <=n$。

多多可以通过随意调整数组$X$中元素的顺序，也可以随意调整字符串$B$中元素的顺序。调整顺序之后，多多需要从左向右遍历数组$X$中的元素，假设当前遍历到的是第$i$个元素，该元素的值为$index_i$，多多就会将字符串$A$中第$index_i$个元素替换为字符串$B$中第$i$个元素;就这样，多多一共会替换$m$次，替换后得到的字符串是$A$'

现在，多多想知道通过调整X中元素的顺序，再调整字符串$B$中元素的顺序后，在所有的可能情况下，如何让替换后得到的字符串 $A$'的字典序最小。

输入描述

第一行输入一个数字$T(1<=T<=10^5$) 表示总共有$T$ 组测试数据,对于每组数据，共有4行

第$1$行输入两个数字$n$和$m,(1<=n,m<=10^5)$，分别表示字符串$A$和$B$的长度

第$2$行输入一个长度为$n$的字符串$A$

第$3$行输入一个长度为$m$的字符串$B$

第$4$行输入一个由$m$个正整数组成的数组$X$，其中第$i$个元素是$index_i(1 <=index_i<=n)$

说明:$T$组测试数据的输入$n$的总和加起来不会超过$3*10^5$，$T$组测试数据的输入$m$的总和加起来也不会超过$3*10^5$

输出描述

对于每组测试数据，输出一行字符串，表示替换后字典序最小的字符串$A$'

补充说明

两个不相等的字符串$S1$和$S2$，$S1$比$S2$字典序小是指:

• $S1$是$S2$的子串
• 或者$S1$和$S2$依次对比每一个字母，出现第一个不相同的字母，并且$S1$中的该字母$<S2$中的该字母。

样例1

输入

3
1 1
a
a
1 
1 2
a
bc
1 1
3 6
pdd
testgo
1 2 3 3 2 1

输出

a
b
ego

说明

共有$3$组测试数据。

第一组测试数据，字符串$B$只有一个字母，数组$X$也只有一个元素，所以替换后的结果是：$a$

第二组测试数据，可以调整字符串$B=cb$,数组$X$={$1,1$}，字符串A的替换变化过程是：$a->c->b$,所以替换后的结果是$b$

第三组测试数据，可以调整字符串$B=tgtose$,数组$X$={$2,2,3, 3,1,1$},字符串$A$的替换过程是:$pdd->ptd -> pgd -> pgt -> pgo -> sgo -> ego$,当然可能也有别的替换方式，这里只列举了其中一种，但最终$A$'最小的是$ego$。