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

public class Main {



static InputStream inputstream = System.in;  
static PrintStream outputstream = System.out;  
static InputReader in = new InputReader(inputstream);  
static PrintWriter out = new PrintWriter(outputstream);

 static tree trees[]=new tree[26];

static char s[];
static int n, q, a, b, k, cnt[]=new int [26];

public static void main(String[] args) {

    while (in.hasNext()) {
    	n=in.nextInt();
    	q=in.nextInt();
        for (int i = 0; i < 26; ++i) {
            trees[i]=new tree(1, n);
        }

       s=in.next().toCharArray();
     
        for (int i = 0; i < s.length; ++i) {
        	//System.out.println(s[i]-'a');
            trees[s[i] - 'a'].update(i + 1, i + 1, 1);
        }

        for (int j = 0; q > j; j++) {
           a=in.nextInt();
           b=in.nextInt();
           k=in.nextInt();
          Arrays.fill(cnt, 0);
            for (int i = 0; i < 26; ++i) {
                cnt[i] = trees[i].query(a, b);
            }
            if (k == 1) {
                int current = a;
                for (int i = 0; i < 26; ++i) {
                    trees[i].update(a, b, 0);
                    trees[i].update(current, current + cnt[i] - 1, 1);
                    current += cnt[i];
                }
            } else {
                int current = a;
                for (int i = 25; 0 <= i; --i) {
                    trees[i].update(a, b, 0);
                    trees[i].update(current, current + cnt[i] - 1, 1);
                    current += cnt[i];
                }
            }
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < 26; ++j) {
                if (trees[j].query(i, i)!=0) {
                    out.print((char)(j + 'a'));
                    break;
                }
            }
        }
        out.println();
        out.flush();
    }

}
}
class tree{
	static  int MAX_SIZE = 100010;
	    int L, R, sum[]=new int[MAX_SIZE << 2], lazy[]=new int[MAX_SIZE << 2];

	 void push_down(int l,int r, int rt) {
	         if (l!=r&& lazy[rt] != -1) {
	        	 int len=r-l+1;
	        //	 System.out.println(rt<<1);
	            sum[rt<<1]=lazy[rt]*(len-(len>>1));
	             lazy[rt<<1] = lazy[rt];
	             sum[rt<<1|1]=lazy [rt]*(len>>1);
	             lazy[rt<<1|1]=lazy[rt];
	             lazy[rt]=-1;
	         }
	     }

	    void push_up(int l,int r,int rt) {
	         
	        if(l!=r)     sum[rt] = sum[rt <<1] + sum[rt <<1|1];
	        
	     }

	     int query(int L, int R, int index,int l, int r) {
	         if (L<=l&&r<=R) {
	             return sum[index];
	         } else {
	             push_down(l,r, index);
	             int ans = 0,m=(l+r)>>1;
	             if (L<=m&&l<=R) {
	                 ans += query(L, R, index<<1,l,m);
	             }
	             if (R>m&&L<=r) {
	                 ans += query(L, R,index<<1|1,m+1,r);
	             }
	             return ans;
	         }
	     }

	     void update(int L, int R, int value,int index, int l, int r) {
	    	// System.out.println(" L ,R "+L+"  "+R);
	    	// System.out.println("l,r"+l+" "+r);
	         if (L<=l&&r<=R) {
	        	// System.out.println("hei");
	           sum[index]=value*(r-l+1);
	           lazy[index]=value;
	           return;
	         }
	         else {
	             push_down(l,r, index);
	             int m=(l+r)>>1;
	      //   System.out.println(m+"  m");
	         if (L<=m&&l<=R) {
	                 update(L, R, value, index<<1,l,m);
	             }
	             if (R>m&&L<=r) {
	                 update(L, R, value, index<<1|1,m+1,r);
	             }
	             push_up(l,r, index);
	         }
	     }
	     tree(int l, int r) {
	         L = l;
	         R = r;
	         Arrays.fill(sum, 0);
	         Arrays.fill(lazy, -1);
	       
	     }

	     int query(int x, int y) {
	    	
	         return query(x,y,1,L, R);
	     }

	     void update(int x, int y, int value) {
	    	
	         update(x,y,value,1,L, R);
	     }
	  }

class InputReader {  
    BufferedReader reader;  
    StringTokenizer tokenizer;  
  
    InputReader(InputStream stream) {  
        reader = new BufferedReader(new InputStreamReader(stream));  
        tokenizer = null;  
    }  
  
    String next() {  
        if (!hasNext())  
            throw new RuntimeException();  
        return tokenizer.nextToken();  
    }  
  
    boolean hasNext() {  
        while (tokenizer == null || !tokenizer.hasMoreTokens())  
            try {  
                tokenizer = new StringTokenizer(reader.readLine());  
            } catch (Exception e) {  
                return false;  
            }  
        return true;  
    }  
  
    long nextLong() {  
        return Long.parseLong(next());  
    }  
  
    int nextInt() {  
        return Integer.parseInt(next());  
    }  
}