A Simple Task

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem Statement

For each query $i,j,k$, sort substring $[i,j]$ ascending when $k=1$ and descending when $k=0$. Print the final string.

Input

The first line contains $n,q$, followed by the lowercase string $S$. Each of the next $q$ lines contains i j k; sort $S[i..j]$ non-decreasing when $k=1$ and non-increasing when $k=0$.

Output

Print the final string.

Subtasks

• Subtask 1 (20%): size and operation count at most 30; all other validity conditions are unchanged.

• Subtask 2 (30%): size and operation count at most 3000; all other validity conditions are unchanged.

• Subtask 3 (50%): full constraints:

• $1\le n\le10^5$

• $0\le q\le50000$

• Chuỗi chỉ gồm chữ thường a..z.

Examples

Input

10 1
agjucbvdfk
1 10 1

Output

abcdfgjkuv

Explanation

Sorting the whole string in increasing order gives abcdfgjkuv.