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 D {
	static char []s,ans;
	
	static int n;
		public static void main(String[] args) throws IOException {
			PrintWriter pw=new PrintWriter(System.out);
			Scanner sc=new Scanner(System.in);
			n=sc.nextInt();
			ans=new char [n];
			int q=sc.nextInt();
			s=sc.nextLine().toCharArray();
			SegmentTree tree=new SegmentTree();
			while(q-->0)
				tree.query(sc.nextInt()-1, sc.nextInt()-1,sc.nextInt());
			
			tree.print();
			pw.println(ans);
			pw.close();
		}
		
		
		static class SegmentTree
		{
			int []state,f[];
			SegmentTree()
			{
				f=new int [26][4*n];
				state=new int [4*n];
				build(1,0,n-1);
			}
			int []merge(int i,int j)
			{
				int []ans=new int [26];
				for(int k=0;k<26;k++)
					ans[k]=f[k][i]+f[k][j];
				return ans;
			}
			int []merge(int []a,int []b)
			{
				int []ans=new int [26];
				for(int k=0;k<26;k++)
					ans[k]=a[k]+b[k];
				return ans;
			}
			void print()
			{
				print(1,0,n-1);
			}
			void print(int node,int tl,int tr)
			{
				if(tl==tr)
				{
					for(int i=0;i<26;i++)
						if(f[i][node]==1)
							ans[tl]=(char)(i+'a');
					return;
				}
				propagate(node, tl, tl+tr>>1, tr);
				int mid=tl+tr>>1;
				print(node*2,tl,mid);
				print(node*2+1,mid+1,tr);
			}
			void build(int node,int tl,int tr)
			{
				state[node]=-1;
				if(tl==tr)
					f[s[tl]-'a'][node]++;
				else
				{
					int mid=tl+tr>>1;
					int left=node<<1,right=left+1;
					build(left,tl,mid);
					build(right,mid+1,tr);
					for(int i=0;i<26;i++)
						f[i][node]=f[i][left]+f[i][right];
				}
				
				
			}
			void query(int l,int r,int k)
			{
				int []f=getFrequency(1,0,n-1,l,r,k);
				
				update(1,0,n-1,l,r,k,f);
			}
			void update(int node,int tl,int tr,int l,int r,int k,int []f2)
			{
				if(r<tl || tr<l )
					return;
				int mid=tl+tr>>1;
				int left=node<<1,right=left+1;
				if(tl>=l && tr<=r)
				{
					int len=tr-tl+1;
					if(k==0)
						for(int i=25;i>=0;i--)
						{
							int x=Math.min(len, f2[i]);
							f2[i]-=x;
							len-=x;
							f[i][node]=x;
						}
					else
						for(int i=0;i<26;i++)
						{
							int x=Math.min(len, f2[i]);
							f2[i]-=x;
							len-=x;
							f[i][node]=x;
						}
				}
				else
				{
					update(left,tl,mid,l,r,k,f2);
					update(right,mid+1,tr,l,r,k,f2);
					for(int i=0;i<26;i++)
						f[i][node]=f[i][left]+f[i][right];
				}

			}
			int [] getFrequency(int node,int tl,int tr,int l,int r,int k)
			{
				if(r<tl || tr<l )
					return new int [26];
			
				int mid=tl+tr>>1;
				int left=node<<1,right=left+1;
				if(tl>=l && tr<=r)
				{
					state[node]=k;
					
					return merge(0,node);
				}
				propagate(node,tl,mid,tr);
				return merge(getFrequency(left,tl,mid,l,r,k),getFrequency(right,mid+1,tr,l,r,k));
				
				
				
				
			}
			void propagate(int node,int tl,int mid,int tr) {
				if(state[node]==-1)
					return;
				
				int len1,len2;
				int left=node<<1,right=left+1;
				int i1,i2;
				if(state[node]==0)
				{
					i1=right;i2=left;
					len1=tr-mid;
					len2=mid-tl+1;
				}
				else {
					i1=left;i2=right;
					len1=mid-tl+1;
					len2=tr-mid;
				}
				for(int i=0;i<26 ;i++)
				{
					int x=Math.min(len1, f[i][node]);
					f[i][i1]=x;
					len1-=x;
				}
				for(int i=25;i>=0;i--)
				{
						int x=Math.min(len2, f[i][node]);
						f[i][i2]=x;
						len2-=x;
				}
				
				state[left]=state[right]=state[node];
				state[node]=-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 Scanner(String s) throws FileNotFoundException {
		br = new BufferedReader(new FileReader(s));
	}
	public int nextInt() throws IOException {
		return Integer.parseInt(next());
	}
	public double nextDouble() throws IOException {
		return Double.parseDouble(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();
	}
}
}