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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class SegmentTree { // 1-based DS, OOP

	int N; // the number of elements in the array as a power of 2 (i.e. after padding)
	int[] array, sTree, lazy;

	SegmentTree(int[] in) {
		array = in;
		N = in.length - 1;
		sTree = new int[N << 1]; // no. of nodes = 2*N - 1, we add one to cross out index zero
		lazy = new int[N << 1];
		Arrays.fill(lazy, -1);
		build(1, 1, N);
	}

	void build(int node, int b, int e) // O(n)
	{
		if (b == e)
			sTree[node] = array[b];
		else {
			int mid = b + e >> 1;
			build(node << 1, b, mid);
			build(node << 1 | 1, mid + 1, e);
			sTree[node] = sTree[node << 1] + sTree[node << 1 | 1];
		}
	}

	void update_point(int index, int val) // O(log n)
	{
		index += N - 1;
		sTree[index]++;
		while (index > 1) {
			index >>= 1;
			sTree[index] = sTree[index << 1] + sTree[index << 1 | 1];
		}
	}

	void update_range(int i, int j, int val) // O(log n)
	{
		update_range(1, 1, N, i, j, val);
	}

	void update_range(int node, int b, int e, int i, int j, int val) {
		if (i > e || j < b)
			return;
		if (b >= i && e <= j) {
			sTree[node] = (e - b + 1) * val;
			lazy[node] = val;
		} else {
			int mid = b + e >> 1;
			propagate(node, b, mid, e);
			update_range(node << 1, b, mid, i, j, val);
			update_range(node << 1 | 1, mid + 1, e, i, j, val);
			sTree[node] = sTree[node << 1] + sTree[node << 1 | 1];
		}

	}

	void propagate(int node, int b, int mid, int e) {
		if(lazy[node]==-1)
			return ;
		lazy[node << 1] = lazy[node];
		lazy[node << 1 | 1] = lazy[node];
		sTree[node << 1] = (mid - b + 1) * lazy[node];
		sTree[node << 1 | 1] = (e - mid) * lazy[node];
		lazy[node] = -1;
	}

	int query(int i, int j) {
		return query(1, 1, N, i, j);
	}

	int query(int node, int b, int e, int i, int j) // O(log n)
	{
		if (i > e || j < b)
			return 0;
		if (b >= i && e <= j)
			return sTree[node];
		int mid = b + e >> 1;
		propagate(node, b, mid, e);
		int q1 = query(node << 1, b, mid, i, j);
		int q2 = query(node << 1 | 1, mid + 1, e, i, j);
		return q1 + q2;

	}

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int q = Integer.parseInt(st.nextToken());
		int N = 1;
		while (N < n)
			N <<= 1;
		SegmentTree[] sg = new SegmentTree[26];
		for (int i = 0; i < sg.length; i++) {
			sg[i] = new SegmentTree(new int[N + 1]);
		}
		char[] a = br.readLine().toCharArray();
		for (int i = 0; i < n; i++) {
			sg[a[i] - 'a'].update_point(i + 1, 1);
		}
		for (int i = 0; i < q; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			int k = Integer.parseInt(st.nextToken());
			if (k == 1) {
				int s = x;
				for (int j = 0; j < 26; j++) {
					int end = (int) sg[j].query(x, y);
//					System.out.println(end);
					sg[j].update_range(x, y, 0);
					sg[j].update_range(s, end + s - 1, 1);
					s = s + end;
				}
			} else {
				int s = y;
				for (int j = 0; j < 26; j++) {
					int end = (int) sg[j].query(x, y);
					sg[j].update_range(x, y, 0);
					sg[j].update_range(s - end + 1, s, 1);
					s = s - end;
				}
			}

		}
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j < 26; j++) {
				if (sg[j].query(i, i) == 1) {
					pw.print((char) (j + 'a'));
					break;
				}
			}
		}

		pw.flush();
	}

}