题目描述

给定一个由小写字母组成的字符串$S$。有$m$次操作，每次操作给定$3$个参数$l,r,x$ 。如果$x=1$，将$S_l\sim S_r$升序排序；如果$x=0$，将$S_l\sim S_r$降序排序。你需要求出最终序列。

输入

第一行两个整数 $n,m$。第二行一个字符串$S$。接下来$m$行每行三个整数$x,l,r$。

输出

一行一个字符串表示答案。

输入样例

5 2 
cabcd 
1 3 1 
3 5 0

输出样例

abdcc

提示

【数据规模】 对于40%的数据，$n,m≤1000$。 对于100%的数据，$n,m≤100000$。

输入顺序说明

操作按题目描述和公开样例读入l,r,x。原输入小节把三者误写为x,l,r；样例首操作1 3 1若依该误写会使l>r，与合法区间矛盾。此处保留原文并说明采用顺序。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。