题目背景

翻译来自于 LibreOJ。

题目描述

题目译自 XXIX Olimpiada Informatyczna – III etap Wybredny Bajtazar

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

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

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

输入格式

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

接下来的 $m$ 行描述颜色调整操作，每行包含一个正整数 $p_{i}$ 和两个不同的小写字母 $a_{i}$ 和 $b_{i}$，用单个空格分隔，表示将前 $p_{i}$ 个颜色为 $a_{i}$ 的灯泡改为颜色 $b_{i}$。你可以假设每次操作前，灯链中至少有 $p_{i}$ 个颜色为 $a_{i}$ 的灯泡。

输出格式

输出一行，包含一个长度为 $n$ 的字符串，由字母 $\texttt{a}$ 到 $\texttt{e}$ 组成，表示所有调整操作完成后灯链上各灯泡的颜色。

10 3
acabbabbac
3 b c
4 a b
3 c a

babaabcbbc

提示

样例解释

灯链颜色变化过程如下：

$$\texttt{acabbabbac} \to \texttt{acaccacbac} \to \texttt{bcbccbcbbc} \to \texttt{babaabcbbc} $$

附加样例

1. 该样例满足 $n=1000, m=1000$，初始灯链为 $\texttt{ababab...ab}$，操作交替进行：将前 $250$ 个 $\tt a$ 改为 $\tt b$，再将前 $250$ 个 $\tt b$ 改为 $\tt a$；
2. 该样例满足 $n=90000, m=100000$，初始灯链为 $\texttt{aaa...abbb...bccc...c}$（每种颜色连续 $30000$ 个），操作循环进行：将前 $10000$ 个 $\texttt{a}$ 改为 $\texttt{b}$，前 $10000$ 个 $\texttt{a}$ 改为 $\texttt{c}$，前 $10000$ 个 $\texttt{b}$ 改为 $\texttt{a}$，前 $10000$ 个 $\texttt{c}$ 改为 $\texttt{a}$；
3. 该样例满足 $n=1000000, m=1000000$，初始灯链为 $\texttt{abcde}$ 重复 $200000$ 次，操作按颜色循环 $\texttt{a} \to \texttt{b} \to \texttt{c} \to \texttt{d} \to \texttt{e} \to \texttt{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$