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.BufferedInputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Map.Entry;
import java.util.Scanner;
import java.util.SortedMap;
import java.util.TreeMap;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(new BufferedInputStream(System.in));
		PrintWriter out = new PrintWriter(System.out);
		int n = in.nextInt(), q = in.nextInt();
		String s = in.next();
		TreeMap<Integer, Pair> tree = new TreeMap<Integer, Pair>();
		for (int i = 1; i <= n; i++) {
			tree.put(i, new Pair(s.charAt(i - 1) - 'a', 1));
		}
		for (int i = 0; i < q; i++) {
			int b = in.nextInt(), e = in.nextInt(), d = in.nextInt();
			int[] length = new int[26];
			Entry<Integer, Pair> head = tree.lowerEntry(b);
			if (head != null) {
				if (head.getKey() + head.getValue().second - 1 <= e) {
					if (head.getKey() + head.getValue().second - 1 >= b) {
						length[head.getValue().first] += head.getKey()
								+ head.getValue().second - b;
						tree.put(head.getKey(), new Pair(head.getValue().first,
								b - head.getKey()));
					}
				} else {
					continue;
				}
			}
			SortedMap<Integer, Pair> interval = tree.subMap(b, e + 1);
			ArrayList<Integer> keys = new ArrayList<Integer>();
			Integer tailKey = null;
			Pair tailValue = null;
			for (Entry<Integer, Pair> entry : interval.entrySet()) {
				if (entry.getKey() + entry.getValue().second - 1 > e) {
					length[entry.getValue().first] += e + 1 - entry.getKey();
					tailKey = e + 1;
					tailValue = new Pair(entry.getValue().first, entry.getKey()
							+ entry.getValue().second - (e + 1));
				} else {
					length[entry.getValue().first] += entry.getValue().second;
				}
				keys.add(entry.getKey());
			}
			for (Integer key : keys) {
				tree.remove(key);
			}
			if (tailKey != null) {
				tree.put(tailKey, tailValue);
			}
			if (d == 1) {
				int key = b;
				for (int j = 0; j < length.length; j++) {
					if (length[j] != 0) {
						tree.put(key, new Pair(j, length[j]));
					}
					key += length[j];
				}
			} else {
				int key = b;
				for (int j = length.length - 1; j >= 0; j--) {
					if (length[j] != 0) {
						tree.put(key, new Pair(j, length[j]));
					}
					key += length[j];
				}
			}
		}
		StringBuilder stringBuilder = new StringBuilder();
		for (Entry<Integer, Pair> entry : tree.entrySet()) {
			for (int _ = 0; _ < entry.getValue().second; _++) {
				stringBuilder.append((char) ('a' + entry.getValue().first));
			}
		}
		out.println(stringBuilder.toString());
		out.close();
		in.close();
	}
}

class Pair implements Comparable<Pair> {
	int first;
	int second;

	Pair(int f, int s) {
		first = f;
		second = s;
	}

	public int compareTo(Pair o) {
		return first - o.first;
	}

}