markdown

E. 简单任务

时间限制：每个测试点 $5$ 秒
内存限制：每个测试点 $512$ MB
输入：标准输入
输出：标准输出

题目描述

本题非常简单。给定一个长度为 $n$ 的字符串 $S$，以及 $q$ 个查询。每个查询的格式为 i j k，含义如下：

• 如果 $k = 1$，则将子串 $S[i..j]$ 按非递减顺序排序；
• 如果 $k = 0$，则将子串 $S[i..j]$ 按非递增顺序排序。

请输出执行完所有查询后的最终字符串。

输入格式

第一行包含两个整数 $n$ 和 $q$（$1 \le n \le 10^5$，$0 \le q \le 50\,000$），分别表示字符串的长度和查询的数量。
第二行包含字符串 $S$，仅由小写英文字母组成。
接下来 $q$ 行，每行包含三个整数 $i$、$j$、$k$（$1 \le i \le j \le n$）。

输出格式

输出一行，即执行完所有查询后的字符串 $S$。

样例

样例输入 1

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

样例输出 1

cbcaaaabdd

样例输入 2

10 1
agjucbvdfk
1 10 1

样例输出 2

abcdfgjkuv

说明

第一个样例的解释略。