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 E implements Runnable {
	public static void main (String[] args) {new Thread(null, new E(), "_cf", 1 << 28).start();}
	
	public void run() {
		FastScanner fs = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		System.err.println("Go!");

//		char[] str = "abacdabcda".toCharArray();
//		int n = str.length;
//		ST st = new ST(n, str);
//		st.doit(0, 3, 2);
//		st.doit(4, 6, 1);
//		st.doit(0, 1, 1);
//		st.findString(1);
//		System.out.println(new String(st.res));
		int n = fs.nextInt();
		int q = fs.nextInt();
		char[] str = fs.next().toCharArray();
		ST st = new ST(n, str);
		while(q-->0) {
			int left = fs.nextInt()-1, right = fs.nextInt()-1;
			int type = fs.nextInt();
			if(type == 0) type = 1;
			else type = 2;
			st.doit(left, right, type);
//			st.findString(1);
//			System.out.println(new String(st.res));
		}
		st.findString(1);
		out.println(new String(st.res));
		
		out.close();
	}
	
	class ST {
		int n;
		int[][] freq;
		int[] push;
		int[] lo, hi;
		char[] res;
		ST(int a, char[] str) {
			n = 4*a+100;
			lo = new int[n];
			hi = new int[n];
			freq = new int[26][n];
			push = new int[n];
			res = new char[a];
			init(1, 0, a-1, str);
		}
		
		void init(int node, int left, int right, char[] str) {
			lo[node] = left; hi[node] = right;
			if(lo[node] == hi[node]) {
				freq[str[left]-'a'][node]++;
				return;
			}
			int mid = (left+right)/2;
			init(2*node, left, mid, str);
			init(2*node+1, mid+1, right, str);
			for(int i = 0; i < 26; i++) {
				freq[i][node] += freq[i][2*node] + freq[i][2*node+1];
			}
		}
		
		void doit(int left, int right, int type) {
			int[] fr = new int[26];
			getSum(1, left, right, fr);
//			System.out.println(Arrays.toString(fr));
			work(1, left, right, fr, type);
//			System.out.println();
		}
		
		void getSum(int node, int left, int right, int[] fr) {
			if(right < lo[node] || left > hi[node]) return;
			if(left <= lo[node] && hi[node] <= right) {
				for(int i = 0; i < 26; i++) fr[i] += freq[i][node];
				return;
			}
			if(push[node] > 0) { push(node, push[node]); push[node] = 0; }
			getSum(2*node, left, right, fr);
			getSum(2*node+1, left, right, fr);
		}
		
		void work(int node, int left, int right, int[] fr, int type) {
			if(hi[node] < left || lo[node] > right) return;
//			System.out.printf("%d [%d, %d] Type: %d FR: %s\n", node, left, right, type, Arrays.toString(fr));
			if(left <= lo[node] && hi[node] <= right) {
//				System.out.println("  Complete covering");
				push[node] = type;
				for(int i = 0; i < 26; i++) freq[i][node] = fr[i];
				return;
			}
			if(push[node] > 0) {
				push(node, push[node]);
				push[node] = 0;
			}
			int[] goLeft = new int[26];
			int[] goRight = new int[26];
			int sum = 0;
			int toLeft = Math.max(0, Math.min(right, hi[2*node]) - Math.max(left, lo[2*node])+1);
			int toRight = Math.max(0, Math.min(right, hi[2*node+1]) - Math.max(left, lo[2*node+1])+1);
//			System.out.printf(" Lf: %d Rg: %d\n", toLeft, toRight);
			for(int i = 0; i < 26; i++) {
				if(type == 1) {
					if(sum < toRight) {
						int min = Math.min(toRight-sum, fr[i]);
						sum += min;
						goRight[i] += min;
						if(sum == toRight) {
							min = fr[i]-min;
							goLeft[i] += min;
						}
					}
					else {
						goLeft[i] += fr[i];
					}
				}
				else {
					if(sum < toLeft) {
						int min = Math.min(toLeft-sum, fr[i]);
						sum += min;
						goLeft[i] += min;
						if(sum == toLeft) {
							min = fr[i]-min;
							goRight[i] += min;
						}
					}
					else {
						goRight[i] += fr[i];
					}
				}
			}
			work(2*node, left, right, goLeft, type);
			work(2*node+1, left, right, goRight, type);
			for(int i = 0; i < 26; i++) freq[i][node] = freq[i][2*node]+freq[i][2*node+1];
		}
		
		void push(int node, int type) {
			//push half the frequency array to left kid
			int sizeLeft = hi[2*node]-lo[2*node]+1;
			int sizeRight = (hi[node]-lo[node]+1)-sizeLeft;
			int[] leftFr = new int[26], rightFr = new int[26];
			int sum = 0;
			for(int i = 0; i < 26; i++) {
				if(type == 1) {
					if(sum < sizeRight) {
						int add = Math.min(sizeRight-sum, freq[i][node]);
						sum += add;
						rightFr[i] += add;
						if(sum == sizeRight) {
							int left = freq[i][node]-add;
							leftFr[i] += left;
						}
					}
					else {
						leftFr[i] += freq[i][node];
					}
				}
				else {
					if(sum < sizeLeft) {
						int add = Math.min(sizeLeft-sum, freq[i][node]);
						sum += add;
						leftFr[i] += add;
						if(sum == sizeLeft) {
							int left = freq[i][node]-add;
							rightFr[i] += left;
						}
					}
					else {
						rightFr[i] += freq[i][node];
					}
				}
			}
			push[2*node] = type;
			push[2*node+1] = type;
			for(int i = 0; i < 26; i++) {
				freq[i][2*node] = leftFr[i];
				freq[i][2*node+1] = rightFr[i];
			}
		}
		
		void findString(int node) {
			if(lo[node] == hi[node]) {
				int fi = -1;
				for(int i = 0; i < 26; i++) if(freq[i][node] > 0) fi = i;
				res[lo[node]] = (char)(fi+'a');
				return;
			}
			if(push[node] > 0) { push(node, push[node]); push[node] = 0; }
			findString(2*node); findString(2*node+1);
		}
		
	}
	
	
	class FastScanner {
		public int BS = 1<<16;
		public char NC = (char)0;
		byte[] buf = new byte[BS];
		int bId = 0, size = 0;
		char c = NC;
		double num = 1;
		BufferedInputStream in;

		public FastScanner() {
			in = new BufferedInputStream(System.in, BS);
		}

		public FastScanner(String s) throws FileNotFoundException {
			in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
		}

		public char nextChar(){
			while(bId==size) {
				try {
					size = in.read(buf);
				}catch(Exception e) {
					return NC;
				}                
				if(size==-1)return NC;
				bId=0;
			}
			return (char)buf[bId++];
		}

		public int nextInt() {
			return (int)nextLong();
		}

		public long nextLong() {
			num=1;
			boolean neg = false;
			if(c==NC)c=nextChar();
			for(;(c<'0' || c>'9'); c = nextChar()) {
				if(c=='-')neg=true;
			}
			long res = 0;
			for(; c>='0' && c <='9'; c=nextChar()) {
				res = (res<<3)+(res<<1)+c-'0';
				num*=10;
			}
			return neg?-res:res;
		}

		public double nextDouble() {
			double cur = nextLong();
			return c!='.' ? cur:cur+nextLong()/num;
		}

		public String next() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c>32) {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public String nextLine() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c!='\n') {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public boolean hasNext() {
			if(c>32)return true;
			while(true) {
				c=nextChar();
				if(c==NC)return false;
				else if(c>32)return true;
			}
		}
		
		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for(int i = 0; i < n; i++) res[i] = nextInt();
			return res;
		}
		
	}

	
}