This task is very simple. Given a string *S* of length *n* and *q* queries each query is on the format *i* *j* *k* which means sort the substring consisting of the characters from *i* to *j* in non-decreasing order if *k* = 1 or in non-increasing order if *k* = 0.

Output the final string after applying the queries.
The first line will contain two integers *n*, *q* (1 ≤ *n* ≤ 10<sup class="upper-index">5</sup>, 0 ≤ *q* ≤ 50 000), the length of the string and the number of queries respectively. 

Next line contains a string *S* itself. It contains only lowercase English letters.

Next *q* lines will contain three integers each *i*, *j*, *k* (1 ≤ *i* ≤ *j* ≤ *n*, <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/187c38b0d200dfc5b5249f93c000f8dee9c1180d.png" style="max-width: 100.0%;max-height: 100.0%;"/>).
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def binary_trie():
    G0, G1, cnt = [-1], [-1], [0]
    return G0, G1, cnt

def insert(x, l):
    j = 0
    for i in range(l, -1, -1):
        cnt[j] += 1
        if x & pow2[i]:
            if G1[j] == -1:
                G0.append(-1)
                G1.append(-1)
                cnt.append(0)
                G1[j] = len(cnt) - 1
            j = G1[j]
        else:
            if G0[j] == -1:
                G0.append(-1)
                G1.append(-1)
                cnt.append(0)
                G0[j] = len(cnt) - 1
            j = G0[j]
    cnt[j] += 1
    return

def erase(x, l):
    j = 0
    for i in range(l, -1, -1):
        cnt[j] -= 1
        if x & pow2[i]:
            j = G1[j]
        else:
            j = G0[j]
    cnt[j] -= 1
    return

def kth_min(k, l):
    j = 0
    ans = 0
    for i in range(l, -1, -1):
        if not G0[j] == -1 and cnt[G0[j]] >= k:
            j = G0[j]
        else:
            ans += pow2[i]
            if not G0[j] == -1:
                k -= cnt[G0[j]]
            j = G1[j]
    return ans

def count_min(k, l):
    j = 0
    ans = 0
    for i in range(l, -1, -1):
        if k & pow2[i]:
            if G0[j] ^ -1:
                ans += cnt[G0[j]]
            j = G1[j]
        else:
            j = G0[j]
    return ans

n, q = map(int, input().split())
s = list(input().rstrip())
s = [-1] + [i - 97 for i in s]
G0, G1, cnt = binary_trie()
l = 17
pow2 = [1]
for _ in range(l):
    pow2.append(2 * pow2[-1])
la = 0
u = [-1] * (n + 1)
v = [-1] * (n + 1)
for i in range(1, n + 1):
    if s[i] ^ s[la]:
        insert(i, l)
        la = i
        v[i] = s[i]
    u[la] = i
for _ in range(q):
    i, j, k = map(int, input().split())
    x = kth_min(count_min(i + 1, l), l)
    if x ^ i:
        insert(i, l)
        u[x], u[i], v[i] = i - 1, u[x], v[x]
    y = kth_min(count_min(j + 1, l), l)
    if u[y] ^ j:
        insert(j + 1, l)
        u[y], u[j + 1], v[j + 1] = j, u[y], v[y]
    z = count_min(i, l) + 1
    c = [0] * 26
    while z <= cnt[0]:
        x = kth_min(z, l)
        if x > j:
            break
        erase(x, l)
        c[v[x]] += u[x] - x + 1
        u[x], v[x] = -1, -1
    if k:
        x, y, z = 0, 26, 1
    else:
        x, y, z = 25, -1, -1
    for j in range(x, y, z):
        if not c[j]:
            continue
        insert(i, l)
        u[i], v[i] = i + c[j] - 1, j
        i += c[j]
i = 1
ans = []
while i <= n:
    ans.append(chr(v[i] + 97) * (u[i] - i + 1))
    i = u[i] + 1
sys.stdout.write("".join(ans))