N. Сортировка кусков

Дана строка из строчных латинских букв и запросы вида «отсортировать подстроку с $i$-й по $j$-ю позицию»: по неубыванию, если $k = 1$, и по невозрастанию, если $k = 0$. Выведите строку после всех запросов.

В первой строке $n$ и $q$ ($1 \le n \le 10^5$, $0 \le q \le 5 \cdot 10^4$). Во второй — строка $S$ из строчных латинских букв длины $n$. Далее $q$ строк по три числа $i$, $j$, $k$ ($1 \le i \le j \le n$, $0 \le k \le 1$).

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