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 start = scanner.nextInt();
			int end = scanner.nextInt();
			int d = scanner.nextInt();
			int[] length = new int[26];

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

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

			// ソートされる区間

			ArrayList<Integer> removeKeys = new ArrayList<>(treeMap.subMap(
					start, end + 1).keySet());

			for (Integer eStart : removeKeys) {
				int eKind = treeMap.get(eStart).kind;
				int eNum = treeMap.get(eStart).num;
				int eEnd = eStart + eNum - 1;

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

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

			// カウンティングソート
			if (d == 1) {
				// 昇順ソートの時
				int key = start;
				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 = start;
				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;
	}
}