题目描述

这个任务非常简单。给定长度为 $n$ 的字符串 $S$ 和 $q$ 个查询，每个查询的格式为 $i,j,k$，表示对从 $i$ 到 $j$ 的子字符串进行排序：

• 如果 $k=1$，则按照非递减顺序排序；
• 如果 $k=0$，则按照非递增顺序排序。

输出应用查询后的最终字符串。

输入格式

第一行包含两个整数 $n,q$，分别表示字符串的长度和查询的数量。

接下来一行包含字符串 $S$。它只包含小写英文字母。

接下来 $q$ 行，每行包含三个整数 $i,j,k$，满足 $1 \le i \le j \le n$，$k \in \{0,1\}$。

输出格式

输出一行，即应用查询后的字符串 $S$。

样例

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

样例解释

第一个样例中：

• 操作 7 10 0：区间 $[7,10]$ 降序排序，abacdabcda 变为 abacdadcba；
• 操作 5 8 1：区间 $[5,8]$ 升序排序，abacdadcba 变为 abacacddba；
• 操作 1 4 0：区间 $[1,4]$ 降序排序，abacacddba 变为 cbaaacddba；
• 操作 3 6 0：区间 $[3,6]$ 降序排序，cbaaacddba 变为 cbcaaaddba；
• 操作 7 10 1：区间 $[7,10]$ 升序排序，cbcaaaddba 变为 cbcaaaabdd。

数据范围与提示

• 对于 $100\%$ 的数据，$1 \le n \le 10^5$，$0 \le q \le 5 \times 10^4$。