Angelina

0

0 votes
Medium
Problem

Angelina is going to a university, so she is busy gathering up her belongings.
Angelina has a younger brother, who is new to programming and wants her help in a question.
Since you are Angelina’s best friend, she has asked you to help her brother.
There is a string of length L and queries n, each query is on the format p q r which intends to sort the characters from p to q in ascending order if r = 1 or in descending order if r = 0.


Input

The first line of input will be an integer T, denoting the number of test cases.
Second line will contain the length of the String L and number of queries n separated by a space.
Next n line will contain queries on format p q r.


Constraint

0< T < 11
1<=L<=100000
0<=q<=50000


OUTPUT

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


Sample Input

1
6 2
cfoypv
4 5 1
1 3 1


Sample Output

cfopyv

Time Limit: 2
Memory Limit: 256
Source Limit:
Editor Image

?