3673. [SYOI 2022 R2]苍空下的乐章

【题目背景】

「瑟尼欧里斯」，极位古圣剑之一，相传是在古战场上奇迹般诞生的神兵利器，现存「遗迹兵器」中最强大的一把剑。

由四十一个护符组成。能将所有事物包含不死者都回归「死亡」（能对被剑伤害的人加上极为复杂的名为“死”的诅咒，连不死之躯都能“杀死”）。

而五百年后，它的能力已经无人可以动用，而剑本身也已经接近支离破碎。

只有现存的唯一一个人类，二等咒器技官「威廉·克梅修」知道它的能力和调整它的方法。

为了在接下来的战斗中让它发挥出全部的力量，威廉需要将它调整到极限状态。

夜晚，威廉带着瑟尼欧里斯，来到浮空岛的边境，在苍空的笼罩下开始了调整工作。

轻轻碰了一块于剑身中段发光的金属片。铿的轻轻一声。金属片自己从剑身卸下以后，便飘浮到半空中，停在离他大约五步远的地方。

在剑柄上注入少许魔力，向护符弹去，宛如演奏铁琴般的清脆金属声响起。光芒陆续飞舞，乐音四起。

【题目描述】

为了方便，可以将护符抽象为 $\text{a} \sim \text{z}$ 的小写字母，排开的护符则可以看做一个长度为 $n$ 的字符串 $s$。

对于调整，威廉可以进行两种操作：

$1\ l\ r\ \text{a}$，表示将 $s_l\ldots s_r$ 全部替换为 $\text{a}$。

$2\ l\ r$，表示将 $s_l\ldots s_r$ 上的字符按字典序升序排序。

（eg.字符串 $\text{dbca}$ 排序后则为 $\text{abcd}$，$\text{plcz}$ 排序后则为 $\text{clpz}$）

现在，威廉想知道，经过 $m$ 次操作后，原先的护符会变成什么样子。

【输入格式】

第一行，两个数 $n$，$m$，表示字符串的长度和操作次数。

接下来一行，一个长为 $n$ 的字符串 $s$。

后面 $m$ 行，每行一种操作，格式和含义见题目描述。

【输出格式】

一个字符串，表示 $s$ 经历 $m$ 次操作后会变为什么样。

【样例输入】

5 3
abacd
1 1 2 c
2 1 5
1 1 1 d

【样例输出】

dcccd

【样例说明】

第一次操作：$\text{ccacd}$

第二次操作：$\text{acccd}$

第三次操作：$\text{dcccd}$

【数据规模与约定】

对于 20% 的数据，$1 \le n,m \le 5\times 10^3$

对于 100% 的数据，$1 \le n,m \le 10^5$，$1 \le l \le r \le n$。

数据均为随机构造。

【来源】

sywb-lgc