#P18813. [Croatian CPC 2026]Cabef Cfeab

[Croatian CPC 2026]Cabef Cfeab

Cabef Cfeab

题目描述

给定一个长度为 NN 的字符串 SS,其中只包含小写英文字母 a、b、c、d、e。你需要依次执行 MM 次操作。

每次操作由一个正整数 pp 和两个不同的字母 x,yx,y 描述:从左往右观察当前字符串,将字母 xx 的前 pp 次出现全部替换成字母 yy。其余字符以及所有字符的相对顺序保持不变。

保证每次操作开始前,当前字符串中至少有 pp 个字母 xx。

请输出执行全部操作后的字符串。

输入格式

第一行包含两个整数 N,MN,M(1≤N,M≤5×1051\le N,M\le5\times10^5),分别表示字符串长度和操作次数。

第二行包含一个长度为 NN 的字符串 SS,仅由 a 至 e 组成,不含空格。

接下来 MM 行,每行包含一个整数 pp(1≤p≤N1\le p\le N)和两个不同的字母 $x,y\in\{\texttt{a},\texttt{b},\texttt{c},\texttt{d},\texttt{e}\}$,用空格分隔。

输出格式

输出一行,为全部操作结束后的字符串,不含空格。

样例 1

输入

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

输出

babaabcbbc

样例 2

输入

10 4
abcdeabcde
1 a e
2 e b
2 b a
1 d c

输出

aaccbabcde

样例 3

输入

1 3
a
1 a e
1 e b
1 b c

输出

c