题目描述

题目译自 XXIX Olimpiada Informatyczna – III etap Wybredny Bajtazar 每年春天一到，Bajtazar 就开始琢磨如何用灯链装饰他的家迎接圣诞节。他拿出了那串陪伴多年的灯链，上面有 $n$ 个灯泡，每盏灯泡有五种颜色之一，用字母 a 到 e 表示。为了让灯链焕然一新，他开始调整每个灯泡的颜色。

调整的过程是这样的：Bajtazar 选定两种颜色 $a$ 和 $b$，以及一个正整数 $p$，然后将从左边数起的前 $p$ 个颜色为 $a$ 的灯泡替换成颜色 $b$。

由于他计划进行多次调整，他请你帮忙编写一个程序，展示在 $m$ 次调整后灯链的样子。

---

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ $(1 \leq n, m \leq 1\,000\,000)$，分别表示灯链中灯泡的数量和颜色调整的次数。
第二行是一个长度为 $n$ 的字符串，由小写字母 a 到 e 组成，表示灯链上各灯泡的初始颜色。

接下来的 $m$ 行描述颜色调整操作，每行包含一个正整数 $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

输出

babaabcbbc

解释
灯链颜色变化过程如下：

acabbabbac → acaccacbac → bcbccbcbbc → babaabcbbc

---

样例 2

见附加文件下 wyb1ocen.in 和 wyb1ocen.out。

该样例满足 $n=1000$, $m=1000$，初始灯链为 ababab...ab，操作交替进行：将前 $250$ 个 a 改为 b，再将前 $250$ 个 b 改为 a。

---

样例 3

见附加文件下 wyb2ocen.in 和 wyb2ocen.out。

该样例满足 $n=90000$, $m=100000$，初始灯链为 aaa...abbb...bccc...c（每种颜色连续 $30000$ 个），操作循环进行：将前 $10000$ 个 a 改为 b，前 $10000$ 个 a 改为 c，前 $10000$ 个 b 改为 a，前 $10000$ 个 c 改为 a。

---

样例 4

见附加文件下 wyb3ocen.in 和 wyb3ocen.out。

该样例满足 $n=1\,000\,000$, $m=1\,000\,000$，初始灯链为 abcde 重复 $200000$ 次，操作按颜色循环 a → b → c → d → e → a，逐步增加调整的灯泡数量。

---

数据范围与提示

子任务编号	附加限制	分值
1	$n \leq 100000$, $m \leq 100$	17
2	$n, m \leq 100000$	18
3	灯链始终只含 a 或 b	29
4	灯链始终只含 a、b 或 c	17
5	无附加限制	19

---

注意

• 颜色只有 5 种（a–e）
• 每次操作保证有足够多的目标颜色灯泡
• 需要高效处理 $10^6$ 级别的 $n$ 和 $m$