题目思路

题目给定的字符串范围是$10^5$，只能使用线性时间的做法，可以直接考虑模拟。

考虑从左到右遍历和从右到左遍历，从左到右遍历时，维护一个距离当前下标最近的偏爱的字符的位置，对于非偏爱字符保存其最近的偏爱字符的位置。

同理，从右到左遍历时，也维护一个距离当前下标最近的偏爱字符的位置，与之前保存的左边最近的偏爱字符位置作比较即可得出答案。

代码

题目描述

小红天生偏爱一些字符，对于一个字符串，他总是想把字符串中的字符变成他偏爱的那些字符。如果字符串中某个字符不是他所偏爱的字符，称为非偏爱字符，那么他会将该非偏爱字符替换为字符串中距离该字符最近的一个偏爱的字符。

这里的距离定义即为字符在字符串中的对应下标之差的绝对值。如果有不止一个偏爱的字符距离非偏爱字符最近，那么小红会选择最左边的那个偏爱字符来替换该非偏爱字符，这样就保证了替换后的字符串是唯一的。小红的所有替换操作是同时进行的。

假定小红有$m$个偏爱的字符，依次为$c_1,c_2,…,c_m$，当小红看到一个长度为$n$的字符串s时，请你输出小红在进行全部替换操作后形成的字符串。

输入描述

第一行输入两个正整数$n，m$。

接下来一行输入$m$个字符$c_1,c_2,…,c_m$，每两个字符之间用空格隔开，表示小红偏爱的字符。接下来一行输入一个字符串s。 $l\le n\le 10^5$，$1 \le m \le26$，保证题目中所有的字符均为大写字符，小红偏爱的字符互不相同，且偏爱字符至少出现一次。

输出描述

输出替换后的字符串

样例

输入输出示例仅供调试，后台判题数据一般不包含示例

输入

5 3
A B C
DAZEC

输出

AAACC