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.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class E {

	static int n;
	static int q;
	static String S;
	
	public static final void main( String[] args ) throws Exception {
		int size = 400005;
		/*SegTree test = new SegTree( 'k' , size );
		String testString = "agjucbvdfk";
		test.build( testString , 1, 0 , testString.length()-1 );
		//test.updateRange( 1 , 0 , testString.length()-1 , 0, 6 , -1 );
		//test.updateRange( 1 , 0 , testString.length()-1 , 0 , 0 , 1 );
		System.out.println( test.queryRange( 1 , 0 , testString.length()-1 , 0 , testString.length()-1 ) );
		//System.out.println( test );
		System.exit( 0 );
		*/
		BufferedReader f = new BufferedReader( new InputStreamReader( System.in ) );
		StringTokenizer st = new StringTokenizer( f.readLine() );
		
		n = Integer.parseInt( st.nextToken() );
		q = Integer.parseInt( st.nextToken() );
		S = f.readLine();
		
		SegTree[] trees = new SegTree[ 26 ];
		for ( int i=0 ; i<26 ; ++i ) {
			trees[ i ] = new SegTree( (char)('a' + i) , size );
			trees[ i ].build( S , 1 , 0 , S.length()-1 );
		}
		
		for ( int idx=0 ; idx<q ; ++idx ) {
			st = new StringTokenizer( f.readLine() );
			int i = Integer.parseInt( st.nextToken() ) - 1;
			int j = Integer.parseInt( st.nextToken() ) - 1;
			int k = Integer.parseInt( st.nextToken() );
			int[] count = new int[ 26 ];
			for ( int letterIdx = 0 ; letterIdx < 26 ; ++letterIdx ) {
				count[ letterIdx ] = trees[ letterIdx ].queryRange( 1 , 0 , S.length()-1 , i , j );
				trees[ letterIdx ].updateRange( 1 , 0 , S.length()-1 , i , j , -1 );
			}
			
			if ( k == 0 ) {
				int nextStart = i;
				for ( int letterIdx = 25 ; letterIdx >= 0 ; --letterIdx ) {
					trees[ letterIdx ].updateRange( 1 , 0 , S.length()-1 , nextStart , nextStart + count[ letterIdx ]-1 , 1 );
					nextStart += count[ letterIdx ];
				}
			}
			else {
				int nextStart = i;
				for ( int letterIdx = 0 ; letterIdx < 26 ; ++letterIdx ) {
					trees[ letterIdx ].updateRange( 1 , 0 , S.length()-1 , nextStart , nextStart + count[ letterIdx ]-1 , 1 );
					nextStart += count[ letterIdx ];
				}
			}
		}
		StringBuilder output = new StringBuilder( "" );
		for ( int i=0 ; i<S.length() ; ++i ) {
			for ( int j=0 ; j<26 ; ++j ) {
				if ( trees[ j ].queryRange( 1 , 0 , S.length()-1 , i , i ) == 1 ) {
					output.append( (char)('a' + j) );
					break;
				}
			}
		}
		System.out.println( output.toString() );
		f.close();
		System.exit( 0 );
	}
	
	static class SegTree {
		
		private final char letter;
		private int[] count;
		
		//1 = consists of only the letter of this tree
		//0 = nothing to be done
		//-1 = consists of no letters of this tree
		private int[] lazyStatus;
		
		public SegTree( char c , int size ) {
			this.letter = c;
			count = new int[ size ];
			lazyStatus = new int[ size ];
		}
		
		public void build( String s , int currNode , int start , int end ) {
			if ( start > end || start >= s.length() ) {
				return;
			}
			
			if ( start == end ) {
				count[ currNode ] = (s.charAt( start ) == letter) ? 1 : 0;
				return;
			}
			
			build( s , currNode*2 , start , (start+end)/2 );
			build( s , currNode*2 + 1 , (start+end)/2 + 1 , end );
			count[ currNode ] = count[ currNode*2 ] + count[ currNode*2+1 ];
		}
		
		//range is inclusive [start, end]
		public int queryRange( int currNode , int nodeStart , int nodeEnd , int queryStart , int queryEnd ) {
			
			//range invalid
			if ( queryStart > queryEnd || currNode >= count.length ) {
				return 0;
			}
			
			if ( lazyStatus[ currNode ] != 0 ) {
				if ( lazyStatus[ currNode ] == 1 ) {
					count[ currNode ] = (nodeEnd - nodeStart) + 1;
				}
				else if ( lazyStatus[ currNode ] == -1 ) {
					count[ currNode ] = 0;
				}
				
				if ( nodeStart != nodeEnd ) {
					lazyStatus[ currNode*2 ] = lazyStatus[ currNode ];
					lazyStatus[ currNode*2 + 1 ] = lazyStatus[ currNode ];
				}
				
				lazyStatus[ currNode ] = 0;
			}
			
			//no overlap
			if ( queryStart > nodeEnd || queryEnd < nodeStart ) {
				return 0;
			}
			
			//perfect overlap
			if ( queryStart == nodeStart && nodeEnd == queryEnd ) {
				return count[ currNode ];
			}
			
			//otherwise, it is overlap, but not perfect overlap
			int leftEnd = Math.min( queryEnd , (nodeStart+nodeEnd)/2 );
			int rtnLeft = queryRange( currNode*2 , nodeStart , (nodeStart+nodeEnd)/2 , queryStart , leftEnd );
			
			int rightStart = Math.max( queryStart , (nodeStart+nodeEnd)/2 + 1 );
			int rtnRight = queryRange( currNode*2+1 , (nodeStart+nodeEnd)/2 + 1 , nodeEnd , rightStart , queryEnd );
			return rtnLeft + rtnRight;
		}
		
		//indicates that [rangeStart, rangeEnd] has the given status
		public void updateRange( int currNode , int nodeStart , int nodeEnd , int rangeStart , int rangeEnd , int status ) {
			
			if ( lazyStatus[ currNode ] != 0 ) {
				if ( lazyStatus[ currNode ] == 1 ) {
					count[ currNode ] = (nodeEnd - nodeStart) + 1;
				}
				else if ( lazyStatus[ currNode ] == -1 ) {
					count[ currNode ] = 0;
				}
				
				if ( nodeStart != nodeEnd ) {
					lazyStatus[ currNode*2 ] = lazyStatus[ currNode ];
					lazyStatus[ currNode*2 + 1 ] = lazyStatus[ currNode ];
				}
				
				lazyStatus[ currNode ] = 0;
			}
			
			//range invalid
			if ( rangeStart > rangeEnd || currNode >= count.length ) {
				return;
			}
			
			//no overlap
			if ( rangeStart > nodeEnd || rangeEnd < nodeStart ) {
				return;
			}
			
			//perfect overlap
			if ( nodeStart == rangeStart && nodeEnd == rangeEnd ) {

				if ( status == 1 ) {
					count[ currNode ] = (nodeEnd - nodeStart) + 1;
					lazyStatus[ currNode ] = 0;
				}
				else if ( status == -1 ) {
					count[ currNode ] = 0;
					lazyStatus[ currNode ] = 0;
				}
				
				if ( nodeStart != nodeEnd ) {
					lazyStatus[ currNode*2 ] = status;
					lazyStatus[ currNode*2 + 1 ] = status;
				}
				return;
			}

			//otherwise, it is partial overlap
			int leftEnd = Math.min( rangeEnd , (nodeStart+nodeEnd)/2 );
			updateRange( currNode*2 , nodeStart , (nodeStart+nodeEnd)/2 , rangeStart , leftEnd , status );
			
			int rightStart = Math.max( rangeStart , (nodeStart+nodeEnd)/2 + 1 );
			updateRange( currNode*2+1 , (nodeStart+nodeEnd)/2 + 1 , nodeEnd , rightStart , rangeEnd , status );
			
			count[ currNode ] = count[ currNode*2 ] + count[ currNode*2 + 1 ];
		}
		
		@Override
		public String toString() {
			return Arrays.toString( this.count );
		}
	}
}