P12921 [POI 2021/2022 R3] 挑剔的 Bajtazar / Wybredny Bajtazar

翻译来自于 [LibreOJ](https://loj.ac/p/4858)。

**题目译自 [XXIX Olimpiada Informatyczna – III etap](https://sio2.mimuw.edu.pl/c/oi29-3/dashboard/) [Wybredny Bajtazar](https://szkopul.edu.pl/problemset/problem/n986eRgmdL0DsqT2Hn5aFDRs/statement/)** 每年春天一到，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}$ 组成，表示所有调整操作完成后灯链上各灯泡的颜色。

**样例解释** 灯链颜色变化过程如下： $$\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$ |