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

public class AsimpleTask {

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int q = sc.nextInt();
		String s = sc.next();
		SegmentTree[] alpha = new SegmentTree[26];
		for (int i = 0; i < 26; i++)
			alpha[i] = new SegmentTree(n + 1);
		for (int i = 0; i < n; i++)
			alpha[s.charAt(i) - 'a'].update_point(i+1, 1);
		while (q-- > 0) {
			int i = sc.nextInt();
			int j = sc.nextInt();
			int k = sc.nextInt();
			int[] cnt = new int[26];
			for (int l = 0; l < 26; l++)
				cnt[l] = alpha[l].query(i, j);
			int p = i - 1;
			if (k == 0) {
				for (int l = 25; l >= 0; l--)
					if (cnt[l] != 0) {
						alpha[l].update(i, j, 0);
						alpha[l].update(p + 1, p + cnt[l], 1);
						p = p + cnt[l];
					}

			} else
				for (int l = 0; l < 26; l++)
					if (cnt[l] != 0) {
						alpha[l].update(i, j, 0);
						alpha[l].update(p + 1, p + cnt[l], 1);
						p = p + cnt[l];
					}

		}
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < n; i++)
			for (int j = 0; j < 26; j++)
				if (alpha[j].query(i + 1, i + 1) != 0) {
					sb.append((Character) (char) (j + 'a'));
					break;
				}
		System.out.println(sb.toString());
	}

	static class SegmentTree {
		int[] tree;
		int[] lazy;
		int N;

		public SegmentTree(int n) {
			N = 1;
			while (N < n)
				N <<= 1;
			tree = new int[N << 1];
			lazy = new int[N << 1];
			Arrays.fill(lazy, -1);
		}

		public void update(int i, int j, int v) {
			update(1, 1, N, i, j, v);
		}

		public void update(int id, int l, int r, int i, int j, int v) {
			if (i > r | j < l)
				return;
			if (i <= l & r <= j) {
				if (v == 1) {
					tree[id] = r - l + 1;
					lazy[id] = 1;
				} else {
					tree[id] = 0;
					lazy[id] = 0;
				}
				return;
			}
			propagate(id, l, r);
			int mid = (l + r) / 2;
			update(id << 1, l, mid, i, j, v);
			update(id << 1 | 1, mid + 1, r, i, j, v);
			tree[id] = tree[id << 1] + tree[id << 1 | 1];
		}

		public void propagate(int id, int l, int r) {
			if (lazy[id] == -1 || l == r)
				return;
			int mid = (l + r) / 2;
			if (lazy[id] == 1) {
				lazy[id << 1] = 1;
				tree[id << 1] = mid - l + 1;
				lazy[id << 1 | 1] = 1;
				tree[id << 1 | 1] = r - mid;
				lazy[id] = -1;
			} else {
				lazy[id << 1] = tree[id << 1] = lazy[id << 1 | 1] = tree[id << 1 | 1] = 0;
				lazy[id] = -1;
			}

		}

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

		public int query(int id, int l, int r, int i, int j) {
			if (i > r | j < l)
				return 0;
			if (i <= l && r <= j)
				return tree[id];
			propagate(id, l, r);
			int mid = (l + r) / 2;
			return query(id << 1, l, mid, i, j) + query(id << 1 | 1, mid + 1, r, i, j);
		}
		void update_point(int index, int val)	
		{
			index += N - 1;				
			tree[index] += val;			
			while(index>1)				
			{
				index >>= 1;
				tree[index] = tree[index<<1] + tree[index<<1|1];		
			}
		}
	}

	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 double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++)
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

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

		public boolean nextEmpty() throws IOException {
			String s = nextLine();
			st = new StringTokenizer(s);
			return s.isEmpty();
		}
	}
}