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

public class Main {
	private final int INF = 1 << 30;

	public void solve() {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int Q = scanner.nextInt();

		String string = scanner.next();

		TreeMap<Integer, Pair> tree = new TreeMap<>();
		for (int i = 0; i < N; i++) {
			tree.put(i + 1, new Pair(string.charAt(i) - 'a', 1));
		}
		for (int q = 0; q < Q; q++) {
			int b = scanner.nextInt();
			int e = scanner.nextInt();
			int d = scanner.nextInt();
			int[] length = new int[26];
			Entry<Integer, Pair> head = tree.lowerEntry(b);
			if (head != null) {
				int hstart = head.getKey();
				int hchar = head.getValue().first;
				int hnum = head.getValue().second;

				if (hstart + hnum - 1 <= e) {
					if (hstart + hnum - 1 >= b) {
						length[hchar] += hstart + hnum - b;
						tree.put(hstart, new Pair(hchar, b - hstart));
					}
				} 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));
			}
		}
		System.out.println(stringBuilder.toString());

	}

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

}

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

	public Pair(int s, int e) {
		this.first = s;
		this.second = e;
	}

	@Override
	public int compareTo(Pair o) {
		if (this.first == o.first) {
			return this.second - o.second;
		}
		return this.first - o.first;
	}
}