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.
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.
0< T < 11
1<=L<=100000
0<=q<=50000
Output one line, the string S after applying the queries.
1
6 2
cfoypv
4 5 1
1 3 1
cfopyv