题目描述

题目译自 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

样例 2

见附加文件下 [wyb1ocen.in](file:wyb1ocen.in) 和 [wyb1ocen.out](file:wyb1ocen.out)。

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

样例 3

见附加文件下 [wyb2ocen.in](file:wyb2ocen.in) 和 [wyb2ocen.out](file:wyb2ocen.out)。

该样例满足 $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}$；

样例 4

见附加文件下 [wyb3ocen.in](file:wyb3ocen.in) 和 [wyb3ocen.out](file:wyb3ocen.out)。

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

数据范围与提示

详细子任务附加限制及分值如下表所示。