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

import java.io.*;
public class cf {
  public static void main(String[] args) throws IOException,InterruptedException{
	Scanner sc =new Scanner(System.in);
	PrintWriter pw = new PrintWriter(System.out);
	SegmentTree[]seg =new SegmentTree[26];
	int n =sc.nextInt(),q=sc.nextInt(),N=1;
	while (n>N)
		N<<=1;
	char[]arr =sc.next().toCharArray();
	for (int i =0;i<26;++i) {
		int [] temp=new int [N+1];
		for (int j =0;j<n;++j)
			temp[j+1]=arr[j]==(char)('a'+i)?1:0;
		seg[i]=new SegmentTree(temp);
	}
	while (q-->0) {
		int l=sc.nextInt(),r=sc.nextInt(),type=sc.nextInt();
		if (type==0) {
			int occ=0;
			for (int i =25;i>=0;--i) {
				int F=seg[i].query(l, r);
				if(F==0)
					continue;
				seg[i].update_range(l, r, 0);
				seg[i].update_range(occ+l, occ+l+F-1, 1);
				occ+=F;
			}
		}else {
			int occ=0;
			for (int i =0;i<26;++i) {
				int F=seg[i].query(l, r);
				if(F==0)
					continue;
				seg[i].update_range(l, r, 0);
				seg[i].update_range(occ+l, occ+l+F-1, 1);
				occ+=F;
			}
		}
	}
	for (int i =1;i<=n;++i)
		for (int j =0;j<26;++j) {
			if (seg[j].query(i, i)==1) {
				pw.print((char)('a'+j));
				break;
			}
		}
    pw.flush();
       }
  static class SegmentTree {		// 1-based DS, OOP
	  
		int N; 			//the number of elements in the array as a power of 2 (i.e. after padding)
		int[] array, sTree, lazy;
	 
		SegmentTree(int[] in)		
		{
			array = in; N = in.length - 1;
			sTree = new int[N<<1];		//no. of nodes = 2*N - 1, we add one to cross out index zero
			lazy = new int[N<<1];
			Arrays.fill(lazy, -1);
			build(1,1,N);
		}
	 
		void build(int node, int b, int e)	// O(n)
		{
			if(b == e)					
				sTree[node] = array[b];
			else						
			{
				int mid = b + e >> 1;
				build(node<<1,b,mid);
				build(node<<1|1,mid+1,e);
				sTree[node] = sTree[node<<1]+sTree[node<<1|1];
			}
		}
	 
		void update_range(int i, int j, int val)		// O(log n) 
		{
			update_range(1,1,N,i,j,val);
		}
	 
		void update_range(int node, int b, int e, int i, int j, int val)
		{
			if(i > e || j < b)		
				return;
			if(b >= i && e <= j)		
			{
				sTree[node] = (e-b+1)*val;			
				lazy[node] = val;				
			}							
			else		
			{
				int mid = b + e >> 1;
				propagate(node, b, mid, e);
				update_range(node<<1,b,mid,i,j,val);
				update_range(node<<1|1,mid+1,e,i,j,val);
				sTree[node] = sTree[node<<1] + sTree[node<<1|1];		
			}
	 
		}
		void propagate(int node, int b, int mid, int e)		
		{
			if (lazy[node]!=-1) {
			lazy[node<<1] = lazy[node];
			lazy[node<<1|1] = lazy[node];
			sTree[node<<1] = (mid-b+1)*lazy[node];		
			sTree[node<<1|1] = (e-mid)*lazy[node];		
			lazy[node] = -1;
			}
		}
	 
		int query(int i, int j)
		{
			return query(1,1,N,i,j);
		}
	 
		int query(int node, int b, int e, int i, int j)	// O(log n)
		{
			if(i>e || j <b)
				return 0;		
			if(b>= i && e <= j)
				return sTree[node];
			int mid = b + e >> 1;
			propagate(node, b, mid, e);
			int q1 = query(node<<1,b,mid,i,j);
			int q2 = query(node<<1|1,mid+1,e,i,j);
			return q1 + q2;	
	 
		}
  } 
  static class Scanner {
		StringTokenizer stringTokenizer;
		BufferedReader bfBufferedReader;
		public Scanner(InputStream system) {
			bfBufferedReader=new BufferedReader(new InputStreamReader( system));
		}
		 public Scanner(String file) throws Exception {
	            bfBufferedReader = new BufferedReader(new FileReader( file));
	        }			 
	        public String next() throws IOException {
	            while (stringTokenizer == null || !stringTokenizer.hasMoreTokens())
	                stringTokenizer = new StringTokenizer( bfBufferedReader.readLine());
	            return stringTokenizer.nextToken();
	        }
	 
	        public String nextLine() throws IOException {
	            return bfBufferedReader.readLine();
	        }
	 
	        public int nextInt() throws IOException {
	            return Integer.parseInt(next());
	        }
	 
	        public double nextDouble() throws IOException {
	            return Double.parseDouble(next());
	        }
	 
	        public char nextChar() throws IOException {
	            return next().charAt(0);
	        }
	 
	        public Long nextLong() throws IOException {
	            return Long.parseLong(next());
	        }
	 
	        public boolean ready() throws IOException {
	            return bfBufferedReader.ready();
	        }
	 
	        public void waitForInput() throws InterruptedException {
	            Thread.sleep(3000);
	        }
  }
}