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

public class CF558E {

	static char[] s;
	static final int INVALID = -1;

	static class SegmentTree {
		int N;
		int[][] sTree, lazy;

		SegmentTree(int n) {
			N = n;
			sTree = new int[N << 1 + 1][26];
			lazy = new int[N << 1 + 1][26];
			for (int i = 0; i < 26; i++)
				build(1, 1, N, i);

			for (int i = 0; i < lazy.length; i++)
				for (int j = 0; j < lazy[i].length; j++)
					lazy[i][j] = INVALID;
		}

		void build(int node, int b, int e, int c) {
			if (b == e) {
				if (b > s.length)
					sTree[node][c] = 0;
				else
					sTree[node][c] = (s[b - 1] == (char) ('a' + c)) ? 1 : 0;
				lazy[node][c] = INVALID;
			} else {
				int mid = (b + e) >> 1;
				build(node << 1, b, mid, c);
				build(node << 1 | 1, mid + 1, e, c);
				sTree[node][c] = sTree[node << 1][c] + sTree[node << 1 | 1][c];
			}
		}

		void update_range(int i, int j, int val, int c) {
			update_range(1, 1, N, i, j, val, c);
		}

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

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

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

		int query(int node, int b, int e, int i, int j, int c) {
			if (i > e || j < b)
				return 0;
			if (b >= i && e <= j)
				return sTree[node][c];
			int mid = (b + e) >> 1;
			propagate(node, b, mid, e, c);
			return query(node << 1, b, mid, i, j, c) + query(node << 1 | 1, mid + 1, e, i, j, c);
		}

		void edit(int c) {
			edit(1, 1, N, c);
		}

		void edit(int node, int b, int e, int c) {
			if (sTree[node][c] == 0)
				return;
			if (b == e) {
				if (b <= s.length)
					s[b - 1] = (char) (c + 'a');
				return;
			}

			int mid = b + e >> 1;
			propagate(node, b, (b + e) >> 1, e, c);
			edit(node << 1, b, mid, c);
			edit(node << 1 | 1, mid + 1, e, c);
		}
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		Scanner sc = new Scanner();
		PrintWriter out = new PrintWriter(System.out);
		int n = sc.nextInt();
		int q = sc.nextInt();
		s = sc.next().toCharArray();

		int N = 1;
		while (N < n)
			N <<= 1;
		SegmentTree st = new SegmentTree(N);

		while (q-- > 0) {
			int[] count = new int[26];
			int s = sc.nextInt();
			int e = sc.nextInt();
			int type = sc.nextInt();
			for (int j = 0; j < 26; j++)
				count[j] = st.query(s, e, j);
			int start = s;
			if (type == 0)
				start = e;

			for (int j = 0; j < 26; j++) {
				if (count[j] == 0)
					continue;
				st.update_range(s, e, 0, j);
				if (type == 0) {
					st.update_range(start - count[j] + 1, start, 1, j);
					start -= count[j];
				} else {
					st.update_range(start, start + count[j] - 1, 1, j);
					start += count[j];
				}
			}

		}

		// build solution
		for (int i = 0; i < 26; i++)
			st.edit(i);
		StringBuilder answer = new StringBuilder();
		for (int i = 0; i < s.length; i++)
			answer.append(s[i]);
		out.println(answer);
		out.flush();
		out.close();
	}

	static class Scanner {
		BufferedReader br;
		StringTokenizer st;

		Scanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		Scanner(String file) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(file));
		}

		String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		int nextInt() throws NumberFormatException, IOException {
			return Integer.parseInt(next());
		}

		String nextLine() throws IOException {
			return br.readLine();
		}

		long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(next());
		}

	}
}