Background

Description

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

Format

Input

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

Output

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

Sample

Input

5 2 
cabcd 
1 3 1 
3 5 0

Output

abdcc

Limitation

对于 40%的数据，n,m<=1000。
对于 100%的数据，n,m<=100000。
1s, 256000KiB for each test case.

Hint

Source

CDQZ TEST