← 返回题目列表

Codeforces · 558/E

E. 一个简单的任务

中文机器翻译题面 查看原题

这个任务非常简单。给定长度为 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$$