C. 更新查询

• 时间限制：每个测试点 $2$ 秒
• 内存限制：每个测试点 $256$ 兆字节

考虑下面这个简单的问题。给定一个长度为 $n$ 的字符串 $s$，由小写拉丁字母组成；一个长度为 $m$ 的索引数组 $\text{ind}$（$1 \le \text{ind}_i \le n$）；以及一个长度为 $m$ 的字符串 $c$，由小写拉丁字母组成。然后，按顺序执行更新操作：在第 $i$ 次操作中，将 $s_{\text{ind}_i}$ 设置为 $c_i$。注意，你从第一次操作到第 $m$ 次操作执行所有 $m$ 次操作。

当然，如果你改变索引数组 $\text{ind}$ 中索引的顺序和/或字符串 $c$ 中字母的顺序，你可以得到不同的结果。求出在你可以任意重排索引数组 $\text{ind}$ 和字符串 $c$ 中的字母的情况下，经过 $m$ 次更新操作后能得到的最小字典序的字符串 $s$。

字符串 $a$ 字典序小于字符串 $b$ 当且仅当满足下列条件之一：

• $a$ 是 $b$ 的前缀，但 $a \ne b$；
• 在 $a$ 和 $b$ 第一个不同的位置上，$a$ 中的字符在字母表中比 $b$ 中的对应字符更靠前。

输入

每个测试包含多组输入数据。第一行包含一个整数 $t$（$1 \le t \le 10^4$）——输入数据的组数。接下来是每组数据的描述。

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

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

每组数据的第三行包含 $m$ 个整数 $\text{ind}_1, \text{ind}_2, \dots, \text{ind}_m$（$1 \le \text{ind}_i \le n$）——索引数组 $\text{ind}$。

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

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

输出

对于每组输入数据，输出通过重排索引数组 $\text{ind}$ 和字符串 $c$ 中的字母所能得到的最小字典序的字符串 $s$。

示例

输入

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

输出

b
cwoz
abdcmbn
ccdeefo

注

• 在第一组数据中，你可以保持索引数组和字符串 $c$ 不变，直接按该顺序执行所有操作。
• 在第二组数据中，你可以设置 $\text{ind} = [1,1,4,2]$ 和 $c = \text{"zczw"}$。那么字符串 $s$ 的变化过程为：$\text{meow} \rightarrow \text{zeow} \rightarrow \text{ceow} \rightarrow \text{ceoz} \rightarrow \text{cwoz}$。
• 在第三组数据中，你可以保持索引数组不变，并设置 $c = \text{"admn"}$。那么字符串 $s$ 的变化过程为：$\text{abacaba} \rightarrow \text{abacaba} \rightarrow \text{abdcaba} \rightarrow \text{abdcmba} \rightarrow \text{abdcmbn}$。