CF558E.A Simple Task

This task is very simple. Given a string S of length n and q queries each query is on the format i j k which means sort the substring consisting of the characters from i to j in non-decreasing order if k = 1 or in non-increasing order if k = 0.

Output the final string after applying the queries.

本题非常简单。给定一个长度为 $n$ 的字符串 $S$，以及 $q$ 个查询，每个查询的格式为 $i$ $j$ $k$，表示：若 $k = 1$，则将 $S$ 中从第 $i$ 个字符到第 $j$ 个字符（包含端点）组成的子串按非递减顺序排序；若 $k = 0$，则按非递增顺序排序。

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

The first line will contain two integers n, q (1 ≤ n ≤ 105, 0 ≤ q ≤ 50 000), the length of the string and the number of queries respectively.

Next line contains a string S itself. It contains only lowercase English letters.

Next q lines will contain three integers each i, j, k (1 ≤ i ≤ j ≤ n, ).

第一行包含两个整数 $n$ 和 $q$（$1 \leq n \leq 10^5$，$0 \leq q \leq 50\,000$），分别表示字符串的长度和查询次数。

下一行包含字符串 $S$ 本身，其中仅包含小写英文字母。

接下来的 $q$ 行每行包含三个整数 $i$、$j$、$k$（$1 \leq i \leq j \leq n$，）。

Output one line, the string S after applying the queries.

输出一行，即对字符串 $S$ 执行所有查询操作后的结果字符串。

First sample test explanation:

第一个样例测试解释：