题目描述

给定一个长度不超过 $10^5$ 的字符串（小写英文字母），和不超过 $50000$ 个操作。

每个操作 L R K 表示给区间 $[L,R]$ 的字符串排序，$K=1$ 为升序，$K=0$ 为降序。

最后输出最终的字符串。

输入格式

第一行两个整数 $n,q$，$1\le n\le 10^5$，$0\le q\le 50000$，分别表示字符串长度、操作次数。

第二行一个长度为 $n$ 的字符串 $s$。

接下来 $q$ 行，每行三个整数，表示一次操作。

输出格式

输出最终的字符串。

10 5
abacdabcda
7 10 0
5 8 1
1 4 0
3 6 0
7 10 1

cbcaaaabdd

10 1
agjucbvdfk
1 10 1

abcdfgjkuv