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.*;
import java.lang.*;
import java.math.*;

import static java.lang.Math.*;

public class Solution implements Runnable {
	
	class SegmentTree {
		int[] a, d;
		int n;
		
		SegmentTree(int[] vals) {
			n = vals.length;
			a = new int[4 * n];
			d = new int[4 * n];
			build(vals, 0, 0, n - 1);
		}
		
		private void build(int[] vals, int v, int tl, int tr) {
			if (tl == tr) {
				a[v] = vals[tl];
				d[v] = 0;
			} else {
				int tm = (tl + tr) / 2;
				build(vals, v * 2 + 1, tl, tm);
				build(vals, v * 2 + 2, tm + 1, tr);
				a[v] = -1;
				d[v] = 0;
			}
		}
		
		void push(int v, int tl, int tm, int tr) {
			a[v * 2 + 1] = a[v];
			d[v * 2 + 1] = d[v];
			
			a[v * 2 + 2] = a[v] + (tm - tl + 1) * d[v];
			d[v * 2 + 2] = d[v];
			a[v] = -1;
			d[v] = 0;
		}
		
		private void update(int v, int tl, int tr, int lf, int rg, int a0, int delta) {
			if (lf > rg) {
				return;
			}
			if (tl == lf && tr == rg) {
				a[v] = a0;
				d[v] = delta;
				return;
			}
			int tm = (tl + tr) / 2;
			if (a[v] != -1) {
				push(v, tl, tm, tr);
			}
			update(v * 2 + 1, tl, tm, lf, min(tm, rg), a0, delta);
			update(v * 2 + 2, tm + 1, tr, max(lf, tm + 1), rg, max(a0, a0 + (tm - lf + 1) * delta), delta);
		}
		
		private int getVal(int v, int tl, int tr, int pos) {
			if (a[v] != -1) {
				return a[v] + (pos - tl) * d[v];
			} else {
				int tm = (tl + tr) / 2;
				if (pos <= tm)
					return getVal(v * 2 + 1, tl, tm, pos);
				else
					return getVal(v * 2 + 2, tm + 1, tr, pos);
			}
		}
		
		void update(int lf, int rg, int a0, int delta) {
			update(0, 0, n - 1, lf, rg, a0, delta);
		}
		
		int getVal(int pos) {
			return getVal(0, 0, n - 1, pos);
		}
	}
	
    void solve() throws Exception {
    	int n = sc.nextInt();
    	int q = sc.nextInt();
    	String s = sc.nextToken();
    	SegmentTree[] t = new SegmentTree[26];
    	for (int i = 0; i < 26; i++) {
    		int[] ar = new int[n + 1];
    		for (int j = 0; j < n; j++) {
    			ar[j + 1] += ar[j];
    			if (s.charAt(j) == (char)('a' + i)) {
    				ar[j + 1]++;
    			}
    		}
    		t[i] = new SegmentTree(ar);
    	}
    	while (q-- > 0) {
    		int lf = sc.nextInt();
    		int rg = sc.nextInt();
    		int sort = sc.nextInt();
    		if (sort == 1) {
    			int lst = lf;
    			for (int i = 0; i < 26; i++) {
    				int tmp = t[i].getVal(lf - 1);
    				int cnt = t[i].getVal(rg) - tmp;
    				if (cnt > 0) {
    					t[i].update(lf, lst, tmp, 0);
	    				t[i].update(lst, lst + cnt - 1, tmp + 1, 1);
	    				t[i].update(lst + cnt, rg, tmp + cnt, 0);
	    				lst += cnt;
    				}
    			}
    		} else {
    			int lst = lf;
    			for (int i = 25; i >= 0; --i) {
    				int tmp = t[i].getVal(lf - 1);
    				int cnt = t[i].getVal(rg) - tmp;
    				if (cnt > 0) {
    					t[i].update(lf, lst, tmp, 0);
	    				t[i].update(lst, lst + cnt - 1, tmp + 1, 1);
	    				t[i].update(lst + cnt, rg, tmp + cnt, 0);
	    				lst += cnt;
    				}
    			}
    		}
    	}
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j < 26; j++) {
    			int cnt = t[j].getVal(i + 1) - t[j].getVal(i);
    			if (cnt == 1) {
    				out.print((char)('a' + j));
    				break;
    			}
    		}
    	}
    	out.println();
    }
    
    BufferedReader in;
    PrintWriter out;
    FastScanner sc;
    
    final String INPUT_FILE = "stdin";
    final String OUTPUT_FILE = "stdout";
    
    static Throwable throwable;
    
    public static void main(String[] args) throws Throwable {
        Thread thread = new Thread(null, new Solution(), "", (1 << 26));
        thread.start();
        thread.join();
        thread.run();
        if (throwable != null)
            throw throwable;
    }
    
    
    public void run() {
        try {
            if (INPUT_FILE.equals("stdin"))
                in = new BufferedReader(new InputStreamReader(System.in));
            else
                in = new BufferedReader(new FileReader(INPUT_FILE));
            if (OUTPUT_FILE.equals("stdout"))
                out = new PrintWriter(System.out);
            else
                out = new PrintWriter(new FileWriter(OUTPUT_FILE));
            sc = new FastScanner(in);
            solve();
        } catch (Exception e) {
            throwable = e;
        } finally {
            out.close();
        }
    }
}

class FastScanner {
    BufferedReader reader;
    StringTokenizer strTok;
    
    FastScanner(BufferedReader reader) {
        this.reader = reader;
    }
    
    public String nextToken() throws Exception {
        while (strTok == null || !strTok.hasMoreTokens())
            strTok = new StringTokenizer(reader.readLine());
        return strTok.nextToken();
    }
    
    public int nextInt() throws Exception {
        return Integer.parseInt(nextToken());
    }
    
    public long nextLong() throws Exception {
        return Long.parseLong(nextToken());
    }
    
    public double nextDouble() throws Exception {
        return Double.parseDouble(nextToken());
    }
}