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%;"/>).
def update(a,x,d):
	l, r, p = 0, n-1, 1
	while l < r:
		mid=(l+r)//2
		if x <= mid:
			r = mid
			p *= 2
		else:
			l = mid+1
			p = p*2+1
	a[p] = d
	while p > 1:
		p = p//2
		a[p] = max(a[p*2], a[p*2+1])
def query(a,x):
	l, r, p = 0, n-1, 1
	s = 0
	while l < r:
		mid=(l+r)//2
		if x <= mid:
			p *= 2
		else:
			s = max(s, a[p*2])
			p = p*2+1
	s = max(s, a[p])
	return s
def split(a, k):
	b = (k, [0 for j in range(26)], a[2])
	c = (a[0] - k, [0 for j in range(26)], a[2])
	if not a[2]:
		k = a[0] - k
		b, c = c, b
	j = 0
	s = 0
	while j < 26 and s < k:
		s += a[1][j]
		j += 1
	j -= 1
	for i in range(j):
		b[1][i] = a[1][i]
	b[1][j] = k - s + a[1][j]
	c[1][j] = s - k
	for i in range(j+1, 26):
		c[1][i] = a[1][i]
	if not a[2]:
		b, c = c, b
	return b, c
n,q=map(int,input().split())
s=input()
a={}
b=[0 for i in range(4*n)]
succ=[0 for i in range(n)]
for i, ch in enumerate(s):
	a[i] = (1, [0 for j in range(26)], 1)
	a[i][1][ord(ch)-97] = 1
	succ[i] = i+1
	update(b,i,i)
for i in range(q):
	x, y, k = map(int, input().split())
	x -= 1
	y -= 1
	z = query(b, x, 0,n-1,1)
	if z < x:
		a[z], a[x] = split(a[z], x - z)
		succ[x] = succ[z]
		succ[z] = x
		update(b,x,x)
	if y+1 < n:
		z = query(b, y+1, 0,n-1,1)
		if z < y+1:
			a[z], a[y+1] = split(a[z], y+1 - z)
			succ[y+1] = succ[z]
			succ[z] = y+1
			update(b,y+1,y+1)
	tmp = [0 for j in range(26)]
	z = x
	while z < y+1:
		if z > x:
			update(b,z,0)
		for j in range(26):
			tmp[j] += a[z][1][j]
		z = succ[z]
	a[x] = (z - x, tmp, k)
	succ[x] = z
i = 0
ans = ''
while i < n:
	tmp = ''
	for j in range(26):
		for k in range(a[i][1][j]):
			tmp += chr(97 + j)
	if not a[i][2]:
		tmp = ''.join(reversed(tmp))
	ans += tmp
	i = succ[i]
print(ans)
