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.*;
import java.util.*;

public class segTree {

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int n = sc.nextInt(), q = sc.nextInt();
		String s = sc.next();
		int size = 1;
		while (size < n)
			size *= 2;
		SegmentTree[] tree = new SegmentTree[26];
		for (int i = 0; i < 26; i++)
			tree[i] = new SegmentTree(size + 1);
		for (int i = 0; i < n; i++)
			tree[s.charAt(i) - 'a'].update_point(i + 1, 1);
		while (q-- > 0) {
			int l = sc.nextInt(), r = sc.nextInt(), inc = sc.nextInt();
			int start = l;
			int a = 0, b = 26, c = 1;
			if (inc == 0) {
				a = 25;
				b = -1;
				c = -1;
			}
			for (int i = a; i != b; i += c) {
				int cnt = tree[i].query(l, r);
//				System.out.print((char) (i + 'a') + " " + cnt + " ");
				if (cnt > 0) {
					tree[i].update_range(l, r, 0);
					tree[i].update_range(start, start + cnt - 1, 1);
					start += cnt;
				}
			}
//			System.out.println();
		}
		for (int i = 1; i <= n; i++)
			for (int j = 0; j < 26; j++)
				if (tree[j].query(i, i) > 0) {
					out.print((char) ('a' + j));
					break;
				}

		out.close();
	}

	static 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 size) {
//			array = new int[size];
			N = size - 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] = val;
			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;
				if (lazy[node] > -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) {
			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;
			if (lazy[node] > -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;

		}
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

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

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

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

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

		public boolean ready() throws IOException {
			return br.ready();
		}
	}
}