这个任务非常简单。给定长度为 n 和 q 的字符串 S,每个查询的格式为 i j k,这意味着如果 k = 1,则按非降序对从 i 到 j 的字符组成的子字符串进行排序;如果 k = 0,则按非升序排序。
应用查询后输出最终字符串。
输入
第一行将包含两个整数n、q (1 ≤ n ≤ 105, 0 ≤ q ≤ 50 000),分别是字符串的长度和查询的数量。
下一行包含字符串 S 本身。它仅包含小写英文字母。
接下来 q 行将包含三个整数,每个 i、j、k (1 ≤ i ≤ j ≤ n, $$k \in \{0, 1\}$$)。
输出
输出一行,应用查询后的字符串 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
注意
第一个样本测试说明:
$$abacda \rightarrow abacdacba$$
$$aba cd adc ba \rightarrow aba cac dd d ba$$
$$abacacddba \rightarrow cbaaacaddbac$$
$$cbaaacddba \rightarrow cbcaaaadba$$
$$cbcaaaadba \rightarrow cbcaaaabdd$$