In KK's point of view,the most important thing for a family is to (die) neatly.

Now given a string of length n（1<=n<=1E5）,which consists only lowercase English letters.

And there is q (0<=q<=5E4)queries,each of which is on the format L、R、K,(0<=L<=R<=n-1)meaning KK wants to sort the substring from L to R in non-decreasing order if K=1 or in non-increasing order if K=0.

Now KK wants to know the final string after applying the queries.As you know,he is too vegetable,so he asks you for help.

There are two integers in the first line, n and q.

In the second line given a string of length n.

In the next q lines, each line means a query.

There are three integers each line, L R K.

1<=n<=1E5,

0<=q<=5E4,

1<=l,r<=n ，l<=r.

Output one line with the final string.

10 5
hbtngdflmj
1 10 1
2 9 0
3 8 1
4 7 0
5 6 1

bnflhjgmdt

Huge input scanf is recommended.