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.*;

public class SimpleTask {
	static int [][] t = new int [26][100010 * 4];
	static int [] p = new int [100010 * 4];
	final static int alpha = 26;
	static String s;
	static int n;

	static void propagate(int c, int b, int e) {
		if(p[c] == -1) return ;

		int m = (b + e) >> 1;
		int l = c << 1;
		int r = l + 1;
		p[l] = p[c];
		p[r] = p[c];
		for(int i = 0; i < alpha; i++) {
			t[i][l] = t[i][r] = 0;
		}
		t[p[c]][l] = (m - b + 1);
		t[p[c]][r] = e - m;
		p[c] = -1;
	}
	static void update(int x, int y, int val, int c, int b, int e) {
		if(x <= b && e <= y) {
			p[c] = val;
			for(int i = 0; i < alpha; i++) {
				t[i][c] = 0;
			}
			t[val][c] = (e - b + 1);
			return ;
		}
		if(y < b || e < x) return ;

		propagate(c, b, e);
		int m = (b + e) >> 1;
		int l = c << 1;
		int r = l + 1;
		update(x, y, val, l, b, m);
		update(x, y, val, r, m+1, e);
		for(int i = 0; i < alpha; i++) {
			t[i][c] = t[i][l] + t[i][r];
		}
		return ;
	}
	static int query(int x, int y, int val, int c, int b, int e) {
		if(x <= b && e <= y) {
			return t[val][c];
		}
		if(y < b || e < x) return 0;

		propagate(c, b, e);
		int m = (b + e) >> 1;
		int l = c << 1;
		int r = l + 1;
		return query(x, y, val, l, b, m) + query(x, y, val, r, m+1, e);
	}
	static char getChar(int x) {
		for(int i = 0; i < alpha; i++) {
			if(query(x, x, i, 1, 1, n) > 0) return (char) (i + 'a');
		}
		return '#';
	}
	static void build(int c, int b, int e) {
		p[c] = -1;
		if(b == e) {
			int val = (int) (s.charAt(b-1) - 'a');
			for(int i = 0; i < alpha; i++) {
				t[i][c] = 0;
			}
			t[val][c] = 1;
			return ;
		}
		int m = (b + e) >> 1;
		int l = c << 1;
		int r = l + 1;
		build(l, b, m);
		build(r, m+1, e);
		for(int i = 0; i < alpha; i++) {
			t[i][c] = t[i][l] + t[i][r];
		}
	}
	static void sort(int l, int r, int asc) {
		int [] count = new int [26];
		for(int i = 0; i < alpha; i++) {
			count[i] = query(l, r, i, 1, 1, n);
		}
		int cur = l;
		if(asc == 1) {
			for(int i = 0; i < alpha; i++) {
				if(count[i] > 0) {
					update(cur, cur + count[i] - 1, i, 1, 1, n);
					cur += count[i];
				}
			}
		} else {
			for(int i = alpha-1; i >= 0; i--) {
				if(count[i] > 0) {
					update(cur, cur + count[i] - 1, i, 1, 1, n);
					cur += count[i];
				}
			}
		}
		return ;
	}
	public static void main (String[] args) {
		Reader in = new Reader ();
		PrintWriter out = new PrintWriter (System.out);

		n = in.nextInt();
		int q = in.nextInt();
		s = in.next();

		build(1, 1, n);
		for(int i = 0; i < q; i++) {
			int l = in.nextInt();
			int r = in.nextInt();
			int k = in.nextInt();
			sort(l, r, k);
		}
		StringBuilder p = new StringBuilder ("");
		for(int i = 1; i <= n; i++) {
			p.append(getChar(i));
		}
		out.println(p);
		out.flush();
		out.close();
	}	
	static class Reader {
		private BufferedReader a;
		private StringTokenizer b;
		Reader() {
			a = new BufferedReader (new InputStreamReader (System.in));
		} 
		public String next () {
			while(b == null || !b.hasMoreTokens()) {
				try {
					 b = new StringTokenizer (a.readLine());
				 } catch (IOException e) {
					 e.printStackTrace();
				 }
			 }
			 return b.nextToken();
		}
		public int nextInt () {
		     return Integer.parseInt(next());
		}
		public long nextLong () {
			return Long.parseLong(next());
		}
		public double nextDouble () {
			return Double.parseDouble(next());
		}
		public String nextLine () {
		 	try {
		 		return a.readLine();
		 	} catch (IOException e) {
		 		e.printStackTrace ();
		 	}
		 	return "##";
		}
	}
	static class Pair <P, Q> {
		P first;
		Q second;
		Pair () {}
		Pair (P first, Q second) {
			this.first = first;
			this.second = second;
		}
	}
}