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.InputStreamReader;
import java.util.Arrays;

public class Main {

	public static int seg[][];
	public static int lazy[][];

	public static void update(int s, int e, int p, int from, int to, int ch, int val) {

		if (lazy[ch][p] != -1) {
			seg[ch][p] = lazy[ch][p] * (e - s + 1);
			if (s != e) {
				lazy[ch][p * 2] = lazy[ch][p];
				lazy[ch][p * 2 + 1] = lazy[ch][p];
			}
			lazy[ch][p] = -1;
		}
		if (s > to || e < from)
			return;
		if (s >= from && e <= to) {
			seg[ch][p] = val * (e - s + 1);
			if (s != e) {
				lazy[ch][p * 2] = val;
				lazy[ch][p * 2 + 1] = val;
			}
			return;
		}
		int mid = (s + e) / 2;
		update(s, mid, p * 2, from, to, ch, val);
		update(mid + 1, e, p * 2 + 1, from, to, ch, val);
		seg[ch][p] = seg[ch][p * 2] + seg[ch][p * 2 + 1];

	}

	public static int get(int s, int e, int p, int ch, int from, int to) {
		if (lazy[ch][p] != -1) {
			seg[ch][p] = lazy[ch][p] * (e - s + 1);
			if (s != e) {
				lazy[ch][p * 2] = lazy[ch][p];
				lazy[ch][p * 2 + 1] = lazy[ch][p];

			}
			lazy[ch][p] = -1;
		}
		if (s > to || e < from)
			return 0;

		if (s >= from && e <= to) {
			return seg[ch][p];
		}
		int mid = (s + e) / 2;
		return get(s, mid, p * 2, ch, from, to) + get(mid + 1, e, p * 2 + 1, ch, from, to);
	}

	public static void main(String[] args) throws IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder e = new StringBuilder();
		String y[] = in.readLine().split(" ");
		int len = Integer.parseInt(y[0]);
		int q = Integer.parseInt(y[1]);
		String a = in.readLine();

		seg = new int[26][len * 4 + 5];
		lazy = new int[26][len * 4 + 5];
		for (int i = 0; i < 26; i++)
			Arrays.fill(lazy[i], -1);

		for (int i = 1; i <= len; i++)
			update(1, len, 1, i, i, a.charAt(i - 1) - 'a', 1);

		for (int i = 0; i < q; i++) {
			y = in.readLine().split(" ");
			int from = Integer.parseInt(y[0]);
			int to = Integer.parseInt(y[1]);
			int f = Integer.parseInt(y[2]);
			int t = from;
			if (f == 0) {
				for (int j = 25; j >= 0; j--) {
					int get = get(1, len, 1, j, from, to);
					if (get != 0) {
						update(1, len, 1, from, to, j, 0);
						update(1, len, 1, t, t + get - 1, j, 1);
						t += get;
					}
				}
			} else {
				for (int j = 0; j < 26; j++) {
					int get = get(1, len, 1, j, from, to);
					if (get != 0) {
						update(1, len, 1, from, to, j, 0);
						update(1, len, 1, t, t + get - 1, j, 1);
						t += get;
					}
				}
			}
		}

		for (int i = 1; i <= len; i++) {
			for (int j = 0; j < 26; j++) {
				int get = get(1, len, 1, j, i, i);
				if (get == 1)
					e.append((char) (j + 'a'));
			}
		}
		System.out.println(e);

	}

}