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.math.*;
public class Solution{
    
    static class SegmentTree{
        int tree[];
        int lazy[];
        
        SegmentTree(int arr[],int n){
            int x = (int)(Math.ceil(Math.log(n)/Math.log(2)));
            int max_size = 2*(int) Math.pow(2,x) - 1;
            tree = new int[max_size];
            lazy = new int[max_size];
            Arrays.fill(lazy,-1);
            
            constructSt(arr,n);
        }
        
        void constructSt(int arr[],int n){
            constructSTUtil(arr,0,n-1,0);
        }
        
        void constructSTUtil(int arr[],int ss,int se,int si){
            if(ss>se) return ;
            if(ss==se) {
                tree[si] = arr[ss];
                return ;
            }
            
            int mid = (ss+se)/2;
            constructSTUtil(arr,ss,mid,si*2+1);
            constructSTUtil(arr,mid+1,se,si*2+2);
            tree[si] = tree[si*2+1] + tree[si*2+2];
        }
        
        void updateRange(int n,int us,int ue,int val){
            updateRangeUtil(0,0,n-1,us,ue,val);
        }
        
        void updateRangeUtil(int si,int ss,int se,int us,int ue,int val){
            
            int mid = (ss+se)/2;
            int first = mid - ss + 1;
            int second = se - mid;
            
            if(lazy[si]!=-1){
                tree[si] = lazy[si];
                if(ss!=se){
                    lazy[si*2+1] = (int) Math.min(first,lazy[si]);
                    lazy[si*2+2] = (int) Math.min(second,lazy[si]);
                }
                lazy[si] = -1;
            }
            
            if(ss>se || ss>ue || se<us) return ;
            if(ss>=us && se<=ue){
                tree[si] = val;
                if(ss!=se){
                    lazy[si*2+1] = (int) Math.min(first,val);
                    lazy[si*2+2] = (int) Math.min(second,val);
                }
                return ;
            }
            
            first = (int) Math.max(0,mid - (int)Math.max(ss,us) + 1);
            second = (int) Math.max(0,(int)Math.min(se,ue) - mid);
            
            updateRangeUtil(si*2+1,ss,mid,us,ue,(int) Math.min(val,first));
            updateRangeUtil(si*2+2,mid+1,se,us,ue,(int) Math.min(val,second));
            
            tree[si] = tree[si*2+1] + tree[si*2+2];
        }
        
        int getSum(int n,int qs,int qe){
            return getSumUtil(0,n-1,qs,qe,0);
        }
        
        int getSumUtil(int ss,int se,int qs,int qe,int si){
            
            int mid = (ss+se)/2;
            int first = mid - ss + 1;
            int second = se - mid;
            
            if(lazy[si]!=-1){
                tree[si] = lazy[si];
                if(ss!=se){
                    lazy[si*2+1] = (int) Math.min(first,lazy[si]);
                    lazy[si*2+2] = (int) Math.min(second,lazy[si]);
                }
                lazy[si] = -1;
            }
            
            if(ss>se || ss>qe || se<qs){
                return 0;
            }
            
            if(ss>=qs && se<=qe) return tree[si];
            return getSumUtil(ss,mid,qs,qe,2*si+1) + getSumUtil(mid+1,se,qs,qe,2*si+2);
        }
    }
        
    
    
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
        
        PrintWriter out = new PrintWriter(System.out);
        
        int n = Integer.parseInt(stk.nextToken());
        int q = Integer.parseInt(stk.nextToken());
        
        String s = br.readLine();
        
        int[][] a = new int[26][n];
        for(int i=0;i<n;i++){
            a[(int)(s.charAt(i)-'a')][i] = 1;
        }
        
        SegmentTree[] st = new SegmentTree[26];
        for(int i=0;i<26;i++) st[i] = new SegmentTree(a[i],n);
        
        for(int i=0;i<q;i++){
            stk = new StringTokenizer(br.readLine());
            int l = Integer.parseInt(stk.nextToken()) - 1;
            int r = Integer.parseInt(stk.nextToken()) - 1;
            int k = Integer.parseInt(stk.nextToken());
            int[] nb = new int[26];
            for(int j=0;j<26;j++) nb[j] = st[j].getSum(n,l,r);
            for(int j=0;j<26;j++) st[j].updateRange(n,l,r,0);
            //if(i==0){
                //for(int j=0;j<26;j++) out.println(nb[j]+" "+st[j].getSum(n,l,r));
            //}
            if(k==1){
                
                for(int j=0;j<26;j++){
                    if(nb[j]==0) continue;
                    st[j].updateRange(n,l,l+nb[j]-1,nb[j]);
                    l += nb[j];
                    
                }
                //if(l>r) out.println(l+"  "+r+"  "+i);
            }else{
                
                for(int j=25;j>=0;j--){
                    if(nb[j]==0) continue;
                    st[j].updateRange(n,l,l+nb[j]-1,nb[j]);
                    l += nb[j];
                }
                
            }
            /*
            if(i==0){
                for(int j=0;j<26;j++) {
                    for(int e=l;e<=r;e++)
                        out.print(st[j].getSum(n,e,e)+" ");
                    out.println("");
                }
                
            }
            */
            //System.out.println("  "+nb[0]);
        }
        
        int[] rep = new int[n];
        for(int i=0;i<n;i++){
            for(int j=0;j<26;j++){
                if(st[j].getSum(n,i,i)==1){
                    rep[i] = j;
                    break;
                }
            }
            //out.print(rep[i]);
            char c = (char) (rep[i]+'a');
            out.print(c);
        }
        out.println("");
        //out.println(st[0].getSum(n,0,n-1));
        out.flush();
        
    }
    
}