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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.StringTokenizer;


public class Main 
{

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		
		ST [] st = new ST[26];
		int n = sc.nextInt();
		int q = sc.nextInt();
		char [] arr = sc.next().toCharArray();
		
		for (int i = 0; i < 26; i++)
			st[i] = new ST(arr, (char)(i + 'a'));
		
		while (q -- > 0) {
			int l = sc.nextInt() - 1, r = sc.nextInt() - 1, op = sc.nextInt();
			int [] cnt = new int[26];
			for (int i = 0; i < 26; i++)
				cnt[i] = st[i].query(1, 0, n - 1, l, r);
			
			if (op == 1) {
				int start = l, end = l-1;
				for (int i = 0; i < 26; i++) {
					start = end + 1;
					end = start + cnt[i] - 1;
					st[i].update(1, 0, n - 1, l, r, 0);
					st[i].update(1, 0, n - 1, start, end, 1);
				}
			}
			else {
				int start = l, end = l-1;
				for (int i = 25; i >= 0; i--) {
					start = end + 1;
					end = start + cnt[i] - 1;
					st[i].update(1, 0, n - 1, l, r, 0);
					st[i].update(1, 0, n - 1, start, end, 1);
				}
			}
		}
		
		StringBuilder res = new StringBuilder();
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < 26; j++) {
				if (st[j].query(1, 0, n - 1, i, i) == 1) {
					res.append((char)(j + 'a'));
					break;
				}
			}
		}
		
		out.println(res);
		out.flush();
		out.close();
	}
	
	

	
	
	
	static class ST {
		char [] arr;
		int [] tree, lazy;
		int n;
		char c;
		ST (char [] a, char cc) {
			arr = a.clone();
			n = arr.length;
			c = cc;
			int pow = 0;
			while (1 << pow < n) pow++;
			tree = new int[(1 << (pow + 1))];
			lazy = new int[(1 << (pow + 1))];
			Arrays.fill(lazy, -1);
			build (1, 0, n - 1);
		}
		
		int query (int node, int s, int e, int l, int r) {
			if (s != e) propagate(node, s, e);
			if (s >= l && e <= r) return tree[node];
			if (s > r || e < l) return 0;
			else {
				int mid = (s + e) >> 1;
				return query(node << 1, s, mid, l, r) +
							query(node << 1 | 1, mid + 1, e, l, r);
			}
		}
		void update (int node, int s, int e, int l, int r, int val) {
			if (s != e) propagate (node, s, e);
			if (s >= l && e <= r) {
				tree[node] = (e - s + 1) * val;
				lazy[node] = val;
			}
			else if (s > r || e < l) return;
			else {
				int mid = (s + e) >> 1;
				update (node << 1, s, mid, l, r, val);
				update (node << 1 | 1, mid + 1, e ,l , r, val);
				tree[node] = tree[node << 1] + tree[node << 1 | 1];
			}
		}
		
		void propagate (int node, int s, int e) {
			if (lazy[node] != -1) {
				lazy[node << 1] = lazy[node];
				lazy[node << 1 | 1] = lazy[node];
				int mid = (s + e) >> 1;
				tree[node << 1] = (mid - s + 1) * lazy[node];
				tree[node << 1 | 1] = (e - (mid + 1) + 1) * lazy[node];
				lazy[node] = -1;
			}
		}
		void build (int node, int s, int e) {
			if (s == e) tree[node] = arr[s] == c ? 1 : 0;
			else {
				int mid = (s + e) >> 1;
				build(node << 1, s, mid);
				build (node << 1 | 1, mid + 1, e);
				tree[node] = tree[node << 1] + tree[node << 1 | 1];
			}
		}
	}
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++)
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

		public boolean ready() throws IOException {
			return br.ready();
		}
		
		public boolean nextEmpty() throws IOException
		{
			String s = nextLine();
			st = new StringTokenizer(s);
			return s.isEmpty();
		}
	}
}