E. Простое задание
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это задание очень простое. Вам дана строка S длины n и q запросов, каждый запрос имеет формат i j k, что означает: отсортировать подстроку, состоящую из символов от i до j, в неубывающем порядке, если k = 1 или в невозрастающем порядке, если k = 0.

Выведите итоговую строку после выполнения запросов.

Входные данные

В первой строке записано два целых числа n, q (1 ≤ n ≤ 105, 0 ≤ q ≤ 50 000), длина строки и количество запросов, соответственно.

В следующей строке идёт сама строка S. Она состоит только из строчных английских букв.

В каждой из следующих q строк записано по три целых числа i, j, k (1 ≤ i ≤ j ≤ n, ), обозначающих запрос.

Выходные данные

Выведите строку S после выполнения всех запросов.

Примеры
Входные данные
10 5
abacdabcda
7 10 0
5 8 1
1 4 0
3 6 0
7 10 1
Выходные данные
cbcaaaabdd
Входные данные
10 1
agjucbvdfk
1 10 1
Выходные данные
abcdfgjkuv
Примечание

Объяснение к первому тесту: