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 Main implements Runnable {
	
	public void solve() throws IOException {
		int N = nextInt();
		int Q = nextInt();
		String s = nextToken();
		
		int[] sum = new int[26];
		SegmentTree sg = new SegmentTree(s);
		for(int i= 0; i < Q; i++){
		    int l = nextInt() - 1;
		    int r = nextInt() - 1;
		    int type = nextInt();
		    sg.get(0, 0, N-1, l, r, sum);
		    sg.set(0, 0, N-1, l, r, sum, type == 1 ? 1 : 2);
		}
		
		sg.print(0, 0, N-1);
		out.println();
	}

	
	
	
	
	
	
	
	
	
	
	
	
	class SegmentTree{;
	    int[][] cnt;
	    int[] type;
	    int[] from, to;
	    // 0 - noth
	    // 1 - incr order
	    // 2 - decr order
	    int n;
	    SegmentTree(String s){
		n = s.length();
		cnt = new int[26][4 * n];
		type = new int[4 * n];
		from = new int[4 * n];
		to = new int[4 * n];
		build(0, 0, n-1, s);
	    }
	    
	    
	    private void update(int v){
		int left = 2 * v + 1, right = 2 * v + 2;
		for(int i = 0; i < 26; i++){
		    cnt[i][v] = cnt[i][left] + cnt[i][right];
		}
	    }
	    
	    private void build(int v, int l, int r, String s){
		from[v] = l;
		to[v] = r;
		if(l == r){
		    cnt[s.charAt(l) - 'a'][v]++;
		}
		else{
		    int m = (l + r) >>> 1;
		    int left = 2 * v + 1; int right = 2 * v + 2;
		    build(left, l, m, s);
		    build(right, m + 1, r, s);
		    update(v);
		}
	    }
	    
	    private void get(int v, int l, int r, int needL, int needR, int[] sum){
		if(needL > needR)
		    return;
		
		if(needL == l && needR == r){
		    for(int i = 0; i < 26; i++){
			sum[i] += cnt[i][v];
		    }
		    return;
		}
		    relax(v, l, r);
		    int m = (l+r) >>> 1;
		    get(v * 2 + 1, l, m, needL, Math.min(needR, m), sum);
		    get(v * 2 + 2, m + 1, r, Math.max(needL, m + 1), needR, sum);
		
	    }
	    
	    private void set(int v, int l, int r, int needL, int needR, int[] sum, int nextType){
		if(needL > needR)
		    return;
		if(needL == l && needR == r){
		    int sz = needR - needL + 1;
		    type[v] = nextType;
		    if(nextType == 1){
			for(int i = 0; i < 26; i++){
			    int more = Math.min(sum[i], sz);
			    sz -= more;
			    sum[i] -= more;
			    cnt[i][v] = more;
			}
		    }
		    else{
			for(int i = 25; i >= 0; i--){
			    int more = Math.min(sum[i], sz);
			    sz -= more;
			    sum[i] -= more;
			    cnt[i][v] = more;
			}
		    }
		    return;
		}
		    relax(v, l, r);
		    int m = (l+r) >>>  1;
		    set(v * 2 + 1, l, m, needL, Math.min(needR, m), sum, nextType);
		    set(v * 2 + 2, m + 1, r, Math.max(needL, m + 1), needR, sum, nextType);
		    update(v);
		
	    }
	    
	    
	    
	    
	    
	    
	    private void relax(int v, int l, int r){
		if(type[v] == 0)
		    return;
		
		if(l == r){
		    type[v] = 0;
		    return;
		}
		int left = 2 * v + 1, right = 2 * v + 2;
		if(type[v] == 1){
		    int szLeft = to[left] - from[left] + 1;
		    for(int i = 0; i < 26; i++){
			int more = Math.min(cnt[i][v], szLeft);
			szLeft -= more;
			cnt[i][left] = more;
		    }
		    int szRight = to[right] - from[right] + 1;
		    for(int i = 25; i >= 0; i--){
			int more = Math.min(cnt[i][v], szRight);
			szRight -= more;
			cnt[i][right] = more;
		    }
		}
		else{
		    int szLeft = to[left] - from[left] + 1;
		    for(int i = 25; i >= 0; i--){
			int more = Math.min(cnt[i][v], szLeft);
			szLeft -= more;
			cnt[i][left] = more;
		    }
		    int szRight = to[right] - from[right] + 1;
		    for(int i = 0; i < 26; i++){
			int more = Math.min(cnt[i][v], szRight);
			szRight -= more;
			cnt[i][right] = more;
		    }
		}

		type[left] = type[right] = type[v];
		type[v] = 0;
	    }
	    
	    private void print(int v, int l, int r){
		relax(v, l, r);
		if(l == r){
		    for(int i = 0; i < 26; i++){
			for(int j = 0; j < cnt[i][v]; j++){
			    out.print((char)('a' + i));
			}
		    }
		}
		else{
		    int m = (l+r) >>> 1;
		    print(v * 2 + 1, l, m);
		    print(v * 2 + 2, m + 1, r);
		}
	    }
	    
	    
	}
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	//-----------------------------------------------------------
	public static void main(String[] args) {
		new Main().run();
	}

        public void debug(Object... arr){
            System.out.println(Arrays.deepToString(arr));
        }

        public void print1Int(int[] a){
                for(int i = 0; i < a.length; i++)
                        System.out.print(a[i] + " ");
                System.out.println();
        }
        
        public void print2Int(int[][] a){
                for(int i = 0; i < a.length; i++){
                        for(int j = 0; j < a[0].length; j++){
                                System.out.print(a[i][j] + " ");
                        }
                        System.out.println();
                }
        }
        
	public void run() {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
                        out = new PrintWriter(System.out);
			tok = null;
			solve();
			in.close();
                        out.close();
		} catch (IOException e) {
			System.exit(0);
		}
	}

	public String nextToken() throws IOException {
		while (tok == null || !tok.hasMoreTokens()) {
			tok = new StringTokenizer(in.readLine());
		}
		return tok.nextToken();
	}

	public int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	public long nextneedLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	public double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}
        PrintWriter out;
	BufferedReader in;
	StringTokenizer tok;
}