Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. A Simple Task

time limit per test

5 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputThis task is very simple. Given a string *S* of length *n* and *q* queries each query is on the format *i* *j* *k* which means sort the substring consisting of the characters from *i* to *j* in non-decreasing order if *k* = 1 or in non-increasing order if *k* = 0.

Output the final string after applying the queries.

Input

The first line will contain two integers *n*, *q* (1 ≤ *n* ≤ 10^{5}, 0 ≤ *q* ≤ 50 000), the length of the string and the number of queries respectively.

Next line contains a string *S* itself. It contains only lowercase English letters.

Next *q* lines will contain three integers each *i*, *j*, *k* (1 ≤ *i* ≤ *j* ≤ *n*, ).

Output

Output one line, the string *S* after applying the queries.

Examples

Input

10 5

abacdabcda

7 10 0

5 8 1

1 4 0

3 6 0

7 10 1

Output

cbcaaaabdd

Input

10 1

agjucbvdfk

1 10 1

Output

abcdfgjkuv

Note

First sample test explanation:

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/20/2017 20:52:58 (c3).

Desktop version, switch to mobile version.

User lists

Name |
---|