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.math.*;
import java.io.*;

public class CF558E {
	class ST {
		int n, h, t[], d[];  boolean[] D;
		public ST(int nn) {
			t = new int[(n = nn) << 1];
			d = new int[n];  D = new boolean[n];
			h = 32 - Integer.numberOfLeadingZeros(n);
		}
		void calc(int p, int k) {
			if(!D[p]) t[p] = t[p << 1] + t[p << 1 | 1];
			else t[p] = d[p] * k;
		}
		void apply(int p, int v, int k) {
			t[p] = v * k;
			if(p < n) { D[p] = true;  d[p] = v; }
		}
		void build(int l, int r) {
			int k = 2;
			for(l += n, r += n - 1 ; l > 1 ; k <<= 1) {
				l >>= 1;  r >>= 1;
				for(int i = r ; i >= l ; i--) calc(i, k);
			}
		}
		void push(int l, int r) {
			int s = h, k = 1 << (h - 1);
			for(l += n, r += n - 1 ; s > 0 ; s--, k >>= 1) {
				for(int i = l >> s ; i <= r >> s ; i++) if(D[i]) {
					apply(i << 1, d[i], k);
					apply(i << 1 | 1, d[i], k);
					D[i] = false;
				}
			}
		}
		void set(int l, int r, int v) { // sets range [l, r) to v
			if(l == r) return;
			push(l, l + 1);  push(r - 1, r);
			int l0 = l, r0 = r, k = 1;
			for(l += n, r += n ; l < r ; l >>= 1,  r >>= 1, k <<= 1) {
				if((l & 1) > 0) apply(l++, v, k);
				if((r & 1) > 0) apply(--r, v, k);
			}
			build(l0, l0 + 1);  build(r0 - 1, r0);
		}
		int query(int l, int r) { // sum query on range [l, r)
			if(l == r) return 0;
			push(l, l + 1);  push(r - 1, r);
			int res = 0;
			for(l += n, r += n ; l < r ; l >>= 1, r >>= 1) {
				if((l & 1) > 0) res += t[l++];
				if((r & 1) > 0) res += t[--r];
			}
			return res;
		}
	}
	public CF558E() {
		System.err.println("Go!");
		FS scan = new FS();
		PrintWriter out = new PrintWriter(System.out);
		int n = scan.nextInt(), q = scan.nextInt();
		char[] s = scan.next().toCharArray();
		ST[] st = new ST[26];
		for(int let = 0 ; let < 26 ; let++)
			st[let] = new ST(n);
		for(int i = 0 ; i < n ; i++) {
			int let = s[i] - 'a';
			st[let].set(i, i + 1, 1);
		}
		for(int qq = 0 ; qq < q ; qq++) {
			int i = scan.nextInt() - 1, j = scan.nextInt(), k = scan.nextInt();
			if(k == 0) { // decreasing
				int l = i;
				for(int let = 25 ; let >= 0 ; let--) {
					int nextl = l + st[let].query(i, j);
					st[let].set(i, j, 0);
					st[let].set(l, nextl, 1);
					l = nextl;
				}
			} else { // increasing
				int l = i;
				for(int let = 0 ; let < 26 ; let++) {
					int nextl = l + st[let].query(i, j);
					st[let].set(i, j, 0);
					st[let].set(l, nextl, 1);
					l = nextl;
				}
			}
		}
		char[] res = new char[n];
		for(int i = 0 ; i < n ; i++)
			for(int let = 0 ; let < 26 ; let++)
				if(st[let].query(i, i + 1) > 0)
					res[i] = (char) (let + 'a');
		out.println(res);
		out.close();
	}
	class FS {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");
		public String next() {
			while(!st.hasMoreTokens()) {
				try { st = new StringTokenizer(br.readLine()); }
				catch(Exception e) { e.printStackTrace(); }
			}
			return st.nextToken();
		}
		public int nextInt() { return Integer.parseInt(next()); }
	}
	public static void main(String[] args) { new CF558E(); }
}
/*

10 1
abacdabcda
3 6 0


*/