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.TreeMap;

public class Main {

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

		String string = scanner.next();

		TreeMap<Integer, Interval> treeMap = new TreeMap<>();
		for (int i = 0; i < N; i++) {
			treeMap.put(i + 1, new Interval(string.charAt(i) - 'a', 1));
		}

		for (int q = 0; q < Q; q++) {
			int qstart = scanner.nextInt();
			int qend = scanner.nextInt();
			int d = scanner.nextInt();
			int[] length = new int[26];

			Entry<Integer, Interval> headInterval = treeMap.lowerEntry(qstart);// startを含む区間を取り出す
			if (headInterval != null) {
				int start = headInterval.getKey();
				int kind = headInterval.getValue().kind;
				int num = headInterval.getValue().num;
				int end = start + num - 1;

				if (end <= qend) {
					if (end >= qstart) {
						length[kind] += start + num - qstart;// ソートに巻きこまれる文字列の数
						treeMap.put(start, new Interval(kind, qstart - start));
					}
				} else {
					// クエリで指定された区間が全て同じ文字だった場合スルーする
					continue;
				}
			}

			// ソートされる区間
			ArrayList<Integer> sortingKeys = new ArrayList<>(treeMap.subMap(
					qstart, qend + 1).keySet());
			for (Integer start : sortingKeys) {
				int kind = treeMap.get(start).kind;
				int num = treeMap.get(start).num;
				int end = start + num - 1;

				if (end > qend) {
					// endを含む区間だった時
					length[kind] += qend + 1 - start;
					treeMap.put(qend + 1, new Interval(kind, end - qend));
				} else {
					// 区間全体がソート対象の場合
					length[kind] += num;
				}

				// ソート対象になった区間は全て削除対象になる
				treeMap.remove(start);
			}

			// カウンティングソート
			if (d == 1) {
				// 昇順ソートの時
				int key = qstart;
				for (int j = 0; j < 26; j++) {
					if (length[j] != 0) {
						treeMap.put(key, new Interval(j, length[j]));
					}
					key += length[j];
				}
			} else {
				int key = qstart;
				for (int j = length.length - 1; j >= 0; j--) {
					if (length[j] != 0) {
						treeMap.put(key, new Interval(j, length[j]));
					}
					key += length[j];
				}
			}
		}
		scanner.close();

		// 出力
		StringBuilder sb = new StringBuilder();
		for (Entry<Integer, Interval> entry : treeMap.entrySet()) {
			for (int i = 0; i < entry.getValue().num; i++) {
				sb.append((char) ('a' + entry.getValue().kind));
			}
		}
		System.out.println(sb.toString());

	}

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

}

class Interval implements Comparable<Interval> {
	int kind, num;

	public Interval(int k, int n) {
		this.kind = k;
		this.num = n;
	}

	@Override
	public int compareTo(Interval o) {
		if (this.kind == o.kind) {
			return this.num - o.num;
		}
		return this.kind - o.kind;
	}
}