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.Scanner;

public class problem5_3 {

	public static void solve(int n, int k, char[] arr, int[][] triples) {
		SegmentTree[] tree = new SegmentTree[26];
		for (int i = 0; i < tree.length; i++) {
			tree[i] = new SegmentTree(arr, (char) (i + 'a'));
		}
		int cnt = 0;
		while(k-- > 0) {
			int a = triples[cnt][0];
			int b = triples[cnt][1];
			if(triples[cnt][2] == 1) {
				int ind = a;
				for(int i = 0; i < 26; i++) {
					int total = tree[i].query(a, b);
					tree[i].update(a, b, -1);
					tree[i].update(ind, ind + total - 1, 1);
					ind += total;
				}
			}else {
				int ind = a;
				for (int i = 25; i >= 0; i--) {
					int total = tree[i].query(a, b);
					tree[i].update(a, b, -1);
					tree[i].update(ind, ind + total - 1, 1);
					ind += total;
				}
			}
			cnt++;
		}
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < 26; j++) {
				if(tree[j].query(i + 1, i + 1) == 1) {
					sb.append((char) (j + 'a'));
				}
			}
		}
		System.out.println(sb);
	}

	public static void main(String[] args) {
		Scanner in = new Scanner((System.in));
		int n = in.nextInt();
		int k = in.nextInt();
		char[] arr = in.next().toCharArray();//new char[n];
		//for (int i = 0; i < n; i++) {
		//	arr[i] = in.next().charAt(0);
		//}
		int[][] triples = new int[k][3];
		for (int i = 0; i < k; i++) {
			triples[i][0] = in.nextInt();
			triples[i][1] = in.nextInt();
			triples[i][2] = in.nextInt();
		}
		solve(n, k, arr, triples);
		in.close();
	}

	static class SegmentTree {
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		//
		int n, arr[], lazy[];
		char in[];

		public SegmentTree(char[] i, char c) {
			n = i.length;
			arr = new int[n << 2];
			lazy = new int[n << 2];
			in = i;
			build(1, 1, n, c);
		}

		int left(int cur) {
			return cur << 1;
		}

		int right(int cur) {
			return cur << 1 | 1;
		}

		void build(int cur, int l, int r, char c) {
			if (l == r)
				arr[cur] = in[l - 1] == c ? 1 : 0;
			else {
				int mid = (l + r) >> 1;
				build(left(cur), l, mid, c);
				build(right(cur), mid + 1, r, c);
				arr[cur] = arr[left(cur)] + arr[right(cur)];
			}
		}

		void update(int l, int r, int val) // value: 1->Set ||| 0->Hold |||
											// -1->Reset
		{
			update(1, 1, n, l, r, val);
		}

		void update(int cur, int l, int r, int lq, int rq, int val) {
			propagate(cur, l, r);
			if (l > rq || r < lq)
				return;
			if (l >= lq && r <= rq) {
				lazy[cur] = val;
				propagate(cur, l, r);
			} else {
				int mid = (l + r) >> 1;
				update(left(cur), l, mid, lq, rq, val);
				update(right(cur), mid + 1, r, lq, rq, val);
				arr[cur] = arr[left(cur)] + arr[right(cur)];
			}
		}

		void propagate(int cur, int l, int r) {
			if (lazy[cur] == 0)
				return;
			if (lazy[cur] == 1)
				arr[cur] = r - l + 1;
			else
				arr[cur] = 0;
			if (l != r) {
				lazy[left(cur)] = lazy[cur];
				lazy[right(cur)] = lazy[cur];
			}
			lazy[cur] = 0;
		}

		int query(int lq, int rq) {
			return query(1, 1, n, lq, rq);
		}

		int query(int cur, int l, int r, int lq, int rq) {
			propagate(cur, l, r);
			if (l > rq || r < lq)
				return 0;
			if (l >= lq && r <= rq)
				return arr[cur];
			int mid = (l + r) >> 1;
			return query(left(cur), l, mid, lq, rq)
					+ query(right(cur), mid + 1, r, lq, rq);
		}
	}
}