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.*;
import java.util.*;
import static java.lang.Math.*;

public class Main {

	BufferedReader in;
	PrintWriter out;
	StringTokenizer tok;

	public static void main(String[] args) {
		new Main().run();
	}

	public void run() {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);
			//Locale.setDefault(Locale.US);
			tok = new StringTokenizer("");
			solve();
			//in.close();
			out.close();
		} catch (Throwable t) {
			t.printStackTrace(System.err);
			System.exit(-1);
		}
	}

	String readString() throws IOException {
		while (!tok.hasMoreTokens()) {
			tok = new StringTokenizer(in.readLine());
		}
		return tok.nextToken();
	}

	int readInt() throws IOException {
		return Integer.parseInt(readString());
	}

	long readLong() throws IOException {
		return Long.parseLong(readString());
	}

	double readDouble() throws IOException {
		return Double.parseDouble(readString());
	}
	
	// solution
	
	static class Item {
		int[] values = new int[26];
		boolean pushed = true;
		int length;
		
		public Item() {}
		
		@Override
		public String toString() {
			return String.format("[%d, %s, %c]", length, Arrays.toString(values), pushed ? 'Y' : 'N');
		}
		
	}

	void solve() throws IOException {
		int n = readInt();
		int queries = readInt();
		Item[] tree = new Item[4*n + 1];
		char[] s = readString().toCharArray();
		build(tree, s, 0, n - 1, 1);
		for (int q = 1; q <= queries; q++) {
			int left = readInt() - 1;
			int right = readInt() - 1;
			int type = readInt();
			if (type == 1) {
				doSortQuery(tree, n, left, right);
			} else {
				doReverseSortQuery(tree, n, left, right);
			}
		}
		printTree(tree, n);
	}

	private void printTree(Item[] tree, int n) {
		for (int i = 0; i < n; i++) {
			out.print(doGetQuery(tree, n, i));
		}
		out.println();
		out.flush();
	}

	private char doGetQuery(Item[] tree, int n, int index) {
		int[] result = get(tree, 1, 0, n - 1, index, index);
		for (int i = 0; i < 26; i++) {
			if (result[i] > 0) {
				return (char) (i + 'a');
			}
		}
		throw new RuntimeException();
	}

	private void doSortQuery(Item[] tree, int n, int left, int right) {
		int[] result = get(tree, 1, 0, n - 1, left, right).clone();
		for (int i = 0; i < 26; i++) {
			if (result[i] > 0) {
				set(tree, 1, 0, n - 1, left, left + result[i] - 1, (char) (i + 'a'));
				left += result[i];
			}
		}
	}

	private void doReverseSortQuery(Item[] tree, int n, int left, int right) {
		int[] result = get(tree, 1, 0, n - 1, left, right).clone();
		for (int i = 25; i >= 0; i--) {
			if (result[i] > 0) {
				set(tree, 1, 0, n - 1, left, left + result[i] - 1, (char) (i + 'a'));
				left += result[i];
			}
		}
	}

	private int[] get(Item[] tree, int treeIndex, int treeLeft, int treeRight, int left, int right) {
		if (treeLeft == left && treeRight == right) {
			return tree[treeIndex].values;
		}
		int treeLeftIndex = 2 * treeIndex;
		int treeRightIndex = 2 * treeIndex + 1;
		push(tree, treeIndex, treeLeftIndex, treeRightIndex);
		int treeMiddle = (treeLeft + treeRight) / 2;
		if (right <= treeMiddle) {
			return get(tree, treeLeftIndex, treeLeft, treeMiddle, left, right);
		} else if (treeMiddle < left) {
			return get(tree, treeRightIndex, treeMiddle + 1, treeRight, left, right);
		} else {
			int[] result = new int[26];
			int[] leftResult = get(tree, treeLeftIndex, treeLeft, treeMiddle, left, treeMiddle);
			int[] rightResult = get(tree, treeRightIndex, treeMiddle + 1, treeRight, treeMiddle + 1, right);
			for (int i = 0; i < 26; i++) {
				result[i] = leftResult[i] + rightResult[i];
			}
			return result;
		}
	}

	private void set(Item[] tree, int treeIndex, int treeLeft, int treeRight, int left, int right, char value) {
		if (treeLeft == left && treeRight == right) {
			Arrays.fill(tree[treeIndex].values, 0);
			tree[treeIndex].values[value - 'a'] = tree[treeIndex].length;
			tree[treeIndex].pushed = false;
			return;
		}
		int treeLeftIndex = 2 * treeIndex;
		int treeRightIndex = 2 * treeIndex + 1;
		push(tree, treeIndex, treeLeftIndex, treeRightIndex);
		int treeMiddle = (treeLeft + treeRight) / 2;
		if (right <= treeMiddle) {
			set(tree, treeLeftIndex, treeLeft, treeMiddle, left, right, value);
		} else if (treeMiddle < left) {
			set(tree, treeRightIndex, treeMiddle + 1, treeRight, left, right, value);
		} else {
			set(tree, treeLeftIndex, treeLeft, treeMiddle, left, treeMiddle, value);
			set(tree, treeRightIndex, treeMiddle + 1, treeRight, treeMiddle + 1, right, value);
		}
		combine(tree, treeIndex, treeLeftIndex, treeRightIndex);
	}

	private void build(Item[] tree, char[] s, int left, int right, int treeIndex) {
		if (tree[treeIndex] == null) {
			tree[treeIndex] = new Item();
		}
		tree[treeIndex].length = right - left + 1;
		if (left == right) {
			tree[treeIndex].values[s[left] - 'a']++;
			return;
		}
		int treeLeftIndex = 2 * treeIndex;
		int treeRightIndex = 2 * treeIndex + 1;
		int middle = (left + right) / 2;
		build(tree, s, left, middle, treeLeftIndex);
		build(tree, s, middle + 1, right, treeRightIndex);
		combine(tree, treeIndex, treeLeftIndex, treeRightIndex);
	}
	
	private void combine(Item[] tree, int treeIndex, int treeLeftIndex, int treeRightIndex) {
		for (int i = 0; i < 26; i++) {
			tree[treeIndex].values[i] = tree[treeLeftIndex].values[i] + tree[treeRightIndex].values[i];
		}
	}

	private void push(Item[] tree, int treeIndex, int treeLeftIndex, int treeRightIndex) {
		if (tree[treeIndex].pushed) {
			return;
		}
		tree[treeIndex].pushed = true;
		if (tree[treeIndex].length == 1) {
			return;
		}
		tree[treeLeftIndex].pushed = false;
		tree[treeRightIndex].pushed = false;
		Arrays.fill(tree[treeLeftIndex].values, 0);
		Arrays.fill(tree[treeRightIndex].values, 0);
		int leftLength = tree[treeLeftIndex].length;
		int leftCount = 0;
		boolean toLeft = true;
		for (int i = 0; i < 26; i++) {
			int curValue = tree[treeIndex].values[i];
			if (toLeft) {
				if (leftCount + curValue <= leftLength) {
					tree[treeLeftIndex].values[i] += curValue;
					leftCount += curValue;
				} else {
					int addToLeft = leftLength - leftCount;
					int addToRight = curValue - addToLeft;
					tree[treeLeftIndex].values[i] += addToLeft;
					tree[treeRightIndex].values[i] += addToRight;
					toLeft = false;
				}
			} else {
				tree[treeRightIndex].values[i] += curValue;
			}
		}
	}

}