Problem: 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.

Input

The first line will contain two integers n, q (1 ≤ n ≤ 105, 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, <image>).

Output

Output one line, the string S after applying the queries.

Examples

Input

10 5
abacdabcda
7 10 0
5 8 1
1 4 0
3 6 0
7 10 1


Output

cbcaaaabdd

Input

10 1
agjucbvdfk
1 10 1


Output

abcdfgjkuv

Note

First sample test explanation:

<image>

<image>

<image>

<image>

<image>

Solution (in JAVA):

Solution:
import java.util.*;
import java.io.*;
import java.awt.Point;
import java.math.BigInteger;

public class simpletask {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int Q = Integer.parseInt(st.nextToken());
		
		char[] line = br.readLine().toCharArray();
		int[] letters = new int[N];
		
		SegmentTree[] count = new SegmentTree[26];
		for(int i = 0; i < 26; i++) count[i] = new SegmentTree(N);
		
		for(int i = 0; i < N; i++) {
			letters[i] = line[i]-'a';
			count[letters[i]].update(1, 0, N-1, i, i, 1);
		}
		
		for(int q = 0; q < Q; q++) {
			int[] counts = new int[26];
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken())-1;
			int b = Integer.parseInt(st.nextToken())-1;
			int c = Integer.parseInt(st.nextToken());
			
			for(int i = 0; i < 26; i++) {
				counts[i] = count[i].query(1, 0, N-1, a, b);
				count[i].clear(1, 0, N-1, a, b);
			}
			
			if(c == 1) {
				int pntr = a;
				for(int i = 0; i < 26; i++) {
					if(counts[i] == 0) continue;
					count[i].update(1, 0, N-1, pntr, pntr+counts[i]-1, 1);
					pntr += counts[i];
				}
			} else {
				int pntr = a;
				for(int i = 25; i >= 0; i--) {
					if(counts[i] == 0) continue;
					count[i].update(1, 0, N-1, pntr, pntr+counts[i]-1, 1);
					pntr += counts[i];
				}
			}
			
		}
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < 26; j++) {
				if(count[j].query(1, 0, N-1, i, i) > 0) { 
					pw.print((char) (j+'a'));
					break;
				}
			}
		}
		
		pw.println();
		pw.close();
	}
	
	static class SegmentTree {
		
		int[] tree;
		int[] lazy;
		boolean[] lazyClear;
		
		public SegmentTree(int N) {
			tree = new int[4*N];
			lazy = new int[4*N];
			lazyClear = new boolean[4*N];
		}
		
		public int query(int vert, int i, int j, int l, int r) {
			if(inside(i, j, l, r)) {
				return lazy[vert]*(j-i+1) + tree[vert];
			}
			
			if(lazyClear[vert]) {
				lazyClear[vert*2] = true;
				lazyClear[vert*2+1] = true;
				lazyClear[vert] = false;
				lazy[vert*2] = 0;
				tree[vert*2] = 0;
				lazy[vert*2+1] = 0;
				tree[vert*2+1] = 0;
			}
			lazy[vert*2] += lazy[vert];
			lazy[vert*2+1] += lazy[vert];
			lazy[vert] = 0;
			
			int ret = 0;
			
			int mid = (i+j)/2;
			
			if(intersects(i, mid, l, r)) {
				ret += query(vert*2, i, mid, l, r);
			}
			if(intersects(mid+1, j, l, r)) {
				ret += query(vert*2+1, mid+1, j, l, r);
			}
			
			tree[vert] = (tree[vert*2] + lazy[vert*2]*(mid-i+1)) + (tree[vert*2+1] + lazy[vert*2+1]*(j-(mid+1)+1));
			
			return ret;
		}
		
		public void clear(int vert, int i, int j, int l, int r) {
			if(inside(i, j, l, r)) {
				lazyClear[vert] = true;
				lazy[vert] = 0;
				tree[vert] = 0;
				return;
			}
			
			if(lazyClear[vert]) {
				lazyClear[vert*2] = true;
				lazyClear[vert*2+1] = true;
				lazyClear[vert] = false;
				lazy[vert*2] = 0;
				tree[vert*2] = 0;
				lazy[vert*2+1] = 0;
				tree[vert*2+1] = 0;
			}
			lazy[vert*2] += lazy[vert];
			lazy[vert*2+1] += lazy[vert];
			lazy[vert] = 0;
			
			int mid = (i+j)/2;
			if(intersects(i, mid, l, r)) {
				clear(vert*2, i, mid, l, r);
			}
			if(intersects(mid+1, j, l, r)) {
				clear(vert*2+1, mid+1, j, l, r);
			}
			
			tree[vert] = (tree[vert*2] + lazy[vert*2]*(mid-i+1)) + (tree[vert*2+1] + lazy[vert*2+1]*(j-(mid+1)+1));
		}
		
		public void update(int vert, int i, int j, int l, int r, int a) {
			if(inside(i, j, l, r)) {
				lazy[vert] += a;
				return;
			}
			
			if(lazyClear[vert]) {
				lazyClear[vert*2] = true;
				lazyClear[vert*2+1] = true;
				lazyClear[vert] = false;
				lazy[vert*2] = 0;
				tree[vert*2] = 0;
				lazy[vert*2+1] = 0;
				tree[vert*2+1] = 0;
			}
			lazy[vert*2] += lazy[vert];
			lazy[vert*2+1] += lazy[vert];
			lazy[vert] = 0;
			
			int mid = (i+j)/2;
			if(intersects(i, mid, l, r)) {
				update(vert*2, i, mid, l, r, a);
			}
			if(intersects(mid+1, j, l, r)) {
				update(vert*2+1, mid+1, j, l, r, a);
			}
			
			tree[vert] = (tree[vert*2] + lazy[vert*2]*(mid-i+1)) + (tree[vert*2+1] + lazy[vert*2+1]*(j-(mid+1)+1));
		}
		
	}
	
	static boolean intersects(int i, int j, int l, int r) {
		return (j >= l) && (i <= r);
	}

	static boolean inside(int inI, int inJ, int l, int r) {
		return (inI >= l) && (inJ <= r);
	}
}