题目描述

字符串消消乐是本次比赛特供给选手的游戏。

与传统消消乐相同，字符串也是从游戏界面上部降下来，进而形成一个矩形消除界面，但是字符串消消乐与传统不同的是消除规则，并不是移动拼凑相同的字符，字符串消消乐的规则是：给出若干匹配规则，如果连续的字符符合匹配规则，那么这段字符可以被消除，如：匹配规则为 "AB" 时，字符串 "FABGI" 中的 "FABGI" 下划线部分 "AB" 可以消除，消除后变为 "FGI"。当然，这个游戏仅一个匹配规则会很单调，因此我们总共会给出 $k$ 条匹配规则。

但是这个游戏是提供给选手娱乐使用的，并非题目，所以主办方决定把他们未解决的问题请选手们解决，进而完善这个游戏。我们会有一列一列随机生成的初始字符串进入游戏页面中，但是对于同一列中可以消除的部分简直是一目了然，所以主办方想将这一部分直接消除掉；具体来讲：你将拿到一个长度为 $n$ 的字符串 $S$，以及 $k$ 条匹配规则 $T_i$，你需要将其中任意时刻符合匹配规则的字符串直接消除掉，保证最终剩下的字符串不会再有符合匹配规则的部分，将这个字符串输出，如果字符串为空请输出 "!" （放心这真的只是一个半角感叹号，不需要输出引号，可以直接复制）。

输入格式

从文件 matchgame.in 中读入数据。

第一行两个正整数 $n,k$，分别表示字符串长度与匹配规则数。

第二行一个字符串 $S$，表示你需要处理的字符串。

接下来共 $k$ 行，第 $i$ 行有一个字符串 $T_i$ 表示第 $i$ 条匹配规则。

输出格式

输出到文件 matchgame.out 中。

一行一个字符串表示最终消除结束的结果，或一个 "!"。

输入样例1

10 1
helloworld
or

输出样例1

hellowld

输入样例2

10 2
helloworld
or
ld

输出样例2

hellow

数据范围

对于 50% 的测试数据，$1 \le n \le 10^3$。

对于 100% 的测试数据，$1 \le n \le 2\times 10^5$，$1\le k\le 5$，每个匹配规则 $T_i$ 的长度不超过 $5$，并且保证所有字符串中仅可能包含大小写字母或数字，匹配规则中不会产生冲突，即不会产生同时有 "AB" 和 "ABC" 这一类的规则。