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 simpleTask {
	static String str;
	static char[] ret;
	static class SegmentTree{
		int n;//length of the string
		int[] tree;
		int[] lazy;
		char c;
		public SegmentTree(int n, char c){
			this.n=n;
			this.c=c;
			int len=2*(int)(Math.pow(2, Math.ceil(Math.log(n)/Math.log(2))))+1;
			//System.out.println(len);
			tree=new int[len];//1-indexed, tree[0] not used
			lazy=new int[len];//1-indexed, lazy[0] not used
			for (int i=1; i<len; i++)
				lazy[i]=-1;
			for (int i=0; i<n; i++){
				if (str.charAt(i)==c) update(i, i, 1);
			}

			//System.out.println("char: "+c+" freq: "+query(0, n-1));
		}

		public void update(int L, int R, int val){//update to val, not add val
			//query(0, n-1);
			//if (L==2 && R==3) System.out.println("tree before: "+Arrays.toString(tree)+"\nlazy before: "+Arrays.toString(lazy));
			updateUtil(1, 0, n-1, L, R, val);
			//interv coords of current considered interv, query interv coords
			//query(0,n-1);
			//if (L==2 && R==3) System.out.println(c+" freq: "+query(0, n-1)+"val: "+val+"tree: "+Arrays.toString(tree)+"\n: "+Arrays.toString(lazy));
		}

		public void updateUtil(int ni, int x, int y, int L, int R, int val){
			//System.out.println(ni+" "+x+" "+y+" "+L+" "+R+" "+val+" "+lazy.length);
			//if (L==2 && R==3) System.out.println("test: "+ni+" "+x+" "+y+" "+L+" "+R+" "+val+" "+Arrays.toString(lazy));
			if (lazy[ni]!=-1){
				tree[ni]=lazy[ni]*(y-x+1);
				if (x!=y){
					lazy[ni*2]=lazy[ni];
					lazy[ni*2+1]=lazy[ni];
				}

				lazy[ni]=-1;
			}

			if (x>=L && y<=R){//cur interv completely inside updated interv
				lazy[ni]=val;
				tree[ni]=lazy[ni]*(y-x+1);//update node ni
				//if (L==2 && R==3 && ni==9) System.out.println("ni 9's coords: "+x+" "+y);
				//if node ni has children, you need to update node ni's children
				if (x!=y){
					lazy[ni*2]=lazy[ni];
					lazy[ni*2+1]=lazy[ni];
				}
				lazy[ni]=-1;
				return;
			}

			if (y<L || x>R) return;//cur interv completely outside updated interv
			//cur interv neither completely inside or outside, therefore must overlap
			updateUtil(ni*2, x, (x+y)/2, L, R, val);
			updateUtil(ni*2+1, 1+(x+y)/2, y, L, R, val);
			tree[ni]=tree[2*ni]+tree[2*ni+1];
			//tree[ni] has to have children because if it is a leaf it will either be completely inside or outside
		}
		public int query(int L, int R){
			return queryUtil(1, 0, n-1, L, R);
		}

		public int queryUtil(int ni, int x, int y, int L, int R){
			if (lazy[ni]!=-1){
				tree[ni]=lazy[ni]*(y-x+1);
				if (x!=y){
					lazy[2*ni]=lazy[ni];
					lazy[2*ni+1]=lazy[ni];
				}
				lazy[ni]=-1;
			}
			if (x>=L && y<=R){
				return tree[ni];
			}
			if (y<L || x>R){
				return 0;
			}

			return queryUtil(ni*2, x, (x+y)/2, L, R)+queryUtil(ni*2+1, 1+(x+y)/2, y, L, R);
		}

		public void get(){
			getUtil(1, 0, n-1);
		}

		public void getUtil(int ni, int x, int y){
			//if (c=='a') System.out.println(lazy[ni]+" "+tree[ni]+" "+x+" "+y);
			if (lazy[ni]!=-1){
				tree[ni]=lazy[ni];
				if (x!=y){
					lazy[2*ni]=lazy[ni];
					lazy[1+2*ni]=lazy[ni];
				}
				lazy[ni]=-1;
			}

			if (x==y){

				if (tree[ni]==1) ret[x]=c;

				return;
			}

			getUtil(ni*2, x, (x+y)/2);
			getUtil(1+ni*2, 1+(x+y)/2, y);
		}
	}
	public static void main(String[] args)throws IOException{
		BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
		String[] ln=(in.readLine()).split(" ");
		int N=Integer.parseInt(ln[0]);
		int Q=Integer.parseInt(ln[1]);
		str=in.readLine();
		ret=new char[N];
		for (int i=0; i<N; i++)
			ret[i]=str.charAt(i);

		SegmentTree[] st=new SegmentTree[26];
		for (int i=0; i<26; i++){
			st[i]=new SegmentTree(N, (char)(i+'a'));
		}
		while (Q-->0){
			ln=(in.readLine()).split(" ");
			int x=Integer.parseInt(ln[0])-1;
			int y=Integer.parseInt(ln[1])-1;
			boolean up=(Integer.parseInt(ln[2])==1);
			//if up then inc else then dec
			int[] cnt=new int[26];//cnt[i] rep number of chars (i+'a') in range [x,y]
			for (int i=0; i<26; i++)
				cnt[i]=st[i].query(x, y);
			//if (x==0 && y==3) System.out.println(Arrays.toString(cnt));//good
			int curr=y;
			if (up) curr=x;
			for (int i=0; i<26; i++){
				if (cnt[i]==0) continue;
				st[i].update(x, y, 0);
				//reset range [x,y] to not have cur char (i+'a')
				if (up){
					st[i].update(curr, curr+cnt[i]-1, 1);
					//if (x==4 && y==7) System.out.println(curr+" "+(curr+cnt[i]-1));
					curr+=cnt[i];
				} else {
					st[i].update(curr-cnt[i]+1, curr, 1);
					curr-=cnt[i];
				}
				//System.out.println(x+" "+y+" "+(char)(i+'a')+" "+st[i].query(0,N-1));
			}
		}

		for (int i=0; i<26; i++){
			st[i].get();
			//System.out.println(Arrays.toString(ret));
		}

		for (int i=0; i<N; i++)
			System.out.print(ret[i]);
		System.out.println();
	}
}
/*
10 1
abacdabcda
1 4 0

*/