和往年一样，从春天开始，Bajtazar 就在考虑用什么样的灯串来装饰他的房子迎接圣诞节。他拿出了自己那串陈旧的灯串，上面有 $n$ 个灯泡。每个灯泡都有五种可用颜色之一，我们用字母 $a$ 到 $e$ 来表示。Bajtazar 开始修改各个灯泡的颜色。
修改操作如下：Bajtazar 选择两种颜色 $a$ 和 $b$ 以及一个正整数 $p$，然后将从左往右数前 $p$ 个颜色为 $a$ 的灯泡改为颜色 $b$。
由于 Bajtazar 计划进行很多次修改，他请求你编写一个程序，展示经过 $m$ 次修改后灯串的样子。
输入格式
输入的第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 1\,000\,000$)，分别表示灯串中灯泡的数量和颜色修改操作的次数。第二行包含一个由 $n$ 个小写英文字母组成的字符串（无空格），表示灯串中各灯泡的颜色。
接下来的 $m$ 行包含颜色修改的描述；其中第 $i$ 行包含一个正整数 $p_i$ 和两个不同的英文小写字母 $a_i$ 和 $b_i$，中间用空格隔开。该行表示需要将前 $p_i$ 个颜色为 $a_i$ 的灯泡改为颜色 $b_i$。你可以假设在操作前，灯串中至少有 $p_i$ 个颜色为 $a_i$ 的灯泡。
输出格式
输出一行，包含一个由 $n$ 个字母（$a$ 到 $e$）组成的字符串（无空格），表示经过所有修改操作后灯串中各灯泡的颜色。
样例
输入格式 1
10 3 acabbabbac 3 b c 4 a b 3 c a
输出格式 1
babaabcbbc
说明
样例解释：灯泡颜色的变化过程如下： $acabbabbac \to acaccacbac \to bcbccbcbbc \to babaabcbbc$。
评分标准
测试集分为以下子任务。每个子任务的测试数据由一组或多组独立的测试用例组成。
| 子任务 | 条件 | 分值 |
|---|---|---|
| 1 | $n \le 100\,000, m \le 100$ | 17 |
| 2 | $n, m \le 100\,000$ | 18 |
| 3 | 灯串仅由颜色 $a$ 或 $b$ 的灯泡组成 | 29 |
| 4 | 灯串仅由颜色 $a, b$ 或 $c$ 的灯泡组成 | 17 |
| 5 | 无附加条件 | 19 |
评测测试
- $n = 1000, m = 1000$，灯串为 $ababab\dots ab$，后续操作交替将前 $250$ 个颜色为 $a$ 的灯泡改为 $b$，以及前 $250$ 个颜色为 $b$ 的灯泡改为 $a$；
- $n = 90\,000, m = 100\,000$，初始灯串为 $aaa\dots abbb\dots bccc\dots c$（每种颜色连续 $30\,000$ 个），后续操作循环将前 $10\,000$ 个颜色为 $a$ 的灯泡改为 $b$，前 $10\,000$ 个颜色为 $a$ 的灯泡改为 $c$，前 $10\,000$ 个颜色为 $b$ 的灯泡改为 $a$，前 $10\,000$ 个颜色为 $c$ 的灯泡改为 $a$；
- $n = 1\,000\,000, m = 1\,000\,000$，初始灯串为 $abcde$ 重复 $200\,000$ 次，后续操作依次增加修改的灯泡数量，并按 $a \to b \to c \to d \to e \to a$ 的循环修改颜色。