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.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader reader;
	static StringTokenizer tokenizer;
	static PrintWriter writer;

	static int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	static long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	static double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}

	static boolean eof = false;

	static String nextToken() throws IOException {
		while (tokenizer == null || !tokenizer.hasMoreTokens()) {
			tokenizer = new StringTokenizer(reader.readLine());
		}
		return tokenizer.nextToken();
	}

	public static void main(String[] args) throws IOException {
		tokenizer = null;
		if (!isDebug) {
			reader = new BufferedReader(new FileReader("input.txt"));
			writer = new PrintWriter(new FileWriter("output.txt"));
		} else {
			reader = new BufferedReader(
			    new InputStreamReader(System.in, "ISO-8859-1"));
			writer = new PrintWriter(System.out);
		}
		banana();
		reader.close();
		writer.close();
	}

	static boolean isDebug = true;

	static int letters = 'z' - 'a' + 1;

	static int n;

	static void init() {
		tree = new Node[4 * n + 5];
		for (int i = 0; i < 4 * n + 5; ++i)
			tree[i] = new Node();
		for (int i = 0; i < letters; ++i)
			build(i, 1, 0, n - 1);
	}

	static String s;

	static void build(int treeIndex, int index, int l, int r) {
		Node cur = tree[index];

		cur.left[treeIndex] = l;
		cur.right[treeIndex] = r;
		cur.length[treeIndex] = r - l + 1;

		if (l == r) {
			cur.sum[treeIndex] = (((s.charAt(l) - 'a') == treeIndex) ? 1 : 0);
			return;
		}

		int m = (l + r) / 2;
		build(treeIndex, 2 * index, l, m);
		build(treeIndex, 2 * index + 1, m + 1, r);

		cur.sum[treeIndex] = tree[2 * index].sum[treeIndex]
		    + tree[2 * index + 1].sum[treeIndex];
	}

	static Node tree[];

	static class Node {
		int left[], right[], sum[], colored[], length[];

		public Node() {
			colored = new int[letters];
			left = new int[letters];
			right = new int[letters];
			sum = new int[letters];
			length = new int[letters];
			Arrays.fill(colored, -1);
		}
	}

	static int sum(int treeIndex, int index) {
		Node cur = tree[index];

		if (cur.left[treeIndex] > r || cur.right[treeIndex] < l)
			return 0;

		push(treeIndex, index);

		if (cur.left[treeIndex] >= l && cur.right[treeIndex] <= r) {
			return cur.sum[treeIndex];
		}

		return sum(treeIndex, 2 * index) + sum(treeIndex, 2 * index + 1);
	}

	static void color(int treeIndex, int index, int value) {
		if (r < l)
			return;

		Node cur = tree[index];

		if (cur.left[treeIndex] > r || cur.right[treeIndex] < l) {
			return;
		}

		if (cur.left[treeIndex] >= l && cur.right[treeIndex] <= r) {
			cur.colored[treeIndex] = value;
			return;
		}

		push(treeIndex, index);

		color(treeIndex, 2 * index, value);
		color(treeIndex, 2 * index + 1, value);
		cur.sum[treeIndex] = 0;

		Node t1 = tree[2 * index];
		Node t2 = tree[2 * index + 1];

		if (t1.colored[treeIndex] != -1)
			cur.sum[treeIndex] += t1.colored[treeIndex] * t1.length[treeIndex];
		else
			cur.sum[treeIndex] += t1.sum[treeIndex];

		if (t2.colored[treeIndex] != -1)
			cur.sum[treeIndex] += t2.colored[treeIndex] * t2.length[treeIndex];
		else
			cur.sum[treeIndex] += t2.sum[treeIndex];
	}

	static void push(int treeIndex, int index) {
		Node cur = tree[index];

		if (cur.colored[treeIndex] != -1) {
			cur.sum[treeIndex] = cur.colored[treeIndex] * cur.length[treeIndex];
			if (cur.left[treeIndex] != cur.right[treeIndex]) {
				tree[2 * index].colored[treeIndex] = tree[2 * index + 1].colored[treeIndex] = cur.colored[treeIndex];
			}
			cur.colored[treeIndex] = -1;
		}
	}

	static int l, r, increace;

	static void banana() throws IOException {
		n = nextInt();
		int q = nextInt();

		s = nextToken();
		init();

		for (int i = 0; i < q; ++i) {
			int ll = nextInt() - 1;
			int rr = nextInt() - 1;
			increace = nextInt();

			int qq[] = new int[letters];

			for (int j = 0; j < letters; ++j) {
				l = ll;
				r = rr;
				qq[j] = sum(j, 1);
				if (qq[j] != 0)
					color(j, 1, 0);
			}

			if (increace == 1) {
				int prev = ll - 1;
				for (int j = 0; j < letters; ++j) {
					l = prev + 1;
					r = l + qq[j] - 1;
					prev = r;
					color(j, 1, 1);
				}
			} else {
				int prev = ll - 1;
				for (int j = letters - 1; j >= 0; --j) {
					l = prev + 1;
					r = l + qq[j] - 1;
					prev = r;
					color(j, 1, 1);
				}
			}
		}

		for (int i = 0; i < n; ++i) {
			l = r = i;
			for (int j = 0; j < letters; ++j) {
				if (sum(j, 1) == 1) {
					writer.print((char) ('a' + j));
					break;
				}
			}
		}
	}
}