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
{
    public static void main (String [] args){
        Scanner add = new Scanner(System.in);
        int length = add.nextInt();
        int consultas = add.nextInt();
        String palabra = add.next();
        int size = 1;
        while(size<length){
            size *=2;
        }
        SegmentTree [] tree = new SegmentTree[26];
        for (int i = 0; i<26; i++){
            tree[i] = new SegmentTree(size+1);
        }
        for(int i = 0;i<length;i++){
            tree[palabra.charAt(i)-'a'].actualizarPunto(i+1,1);
        }
        while(consultas-- > 0){
            int ini = add.nextInt();
            int fin= add.nextInt();
            int forma = add.nextInt();
            int start = ini;
            int a=0;
            int b=26;
            int c=1;
            if(forma==0){
                a = 25;
                b = -1;
                c = -1;
            }
            for(int i=a; i!=b; i+=c){
                int cnt = tree[i].consulta(ini,fin);
                if(cnt>0){
                    tree[i].actualizarRango(ini,fin,0);
                    tree[i].actualizarRango(start,start + cnt -1,1);
                    start += cnt;
                }
            }
        }
        for(int i = 1; i<=length;i++){
            for(int j=0;j<26;j++){
                if(tree[j].consulta(i,i)>0){
                    System.out.print((char)('a'+j));
                }
            }
        }
    }
    
    public static class SegmentTree{
        int N;
        int [] array;
        int [] arbol;
        int [] lazy;
        SegmentTree(int tamanio){
            N = tamanio-1;
            arbol = new int[N<<1];
            lazy = new int[N<<1];
            Arrays.fill(lazy,-1);
        }
        
        public void iniciar(int nodo, int b, int e){
            if(b==e){
                arbol[nodo] = array[b];
            }
            else{
                int mid = b + e>>1;
                iniciar(nodo<<1,b,mid);
                iniciar(nodo<<1|1,mid+1,e);
                arbol[nodo] = arbol[nodo<<1] + arbol[nodo<<1|1];
            }
        }
        
        public void actualizarPunto(int index, int val){
            index += N -1;
            arbol[index] = val;
            while(index>1){
                index >>=1;
                arbol[index] = arbol[index<<1] + arbol[index<<1|1];
            }
        }
        
        public void actualizarRango(int i, int j, int val){
            actualizarRango(1,1,N,i,j,val);
        }
        
        public void actualizarRango(int nodo, int b, int e,int i,int j,int val){
            if(i>e || j<b)
                return;
            if(b>=i && e<=j){
                arbol[nodo] = (e-b+1)*val;
                lazy[nodo] = val;
            } else{
                int mid = b+e>>1;
                if(lazy[nodo]>-1)
                    propagar(nodo,b,mid,e);
                actualizarRango(nodo<<1,b,mid,i,j,val);
                actualizarRango(nodo<<1|1,mid+1,e,i,j,val);
                arbol[nodo] = arbol[nodo<<1] + arbol[nodo<<1|1];
            }
        }
        
        public void propagar(int nodo, int b, int mid, int e){
            lazy[nodo<<1] = lazy[nodo];
            lazy[nodo<<1|1] = lazy[nodo];
            arbol[nodo<<1] = (mid-b+1) * lazy[nodo];
            arbol[nodo<<1|1] = (e-mid) * lazy[nodo];
            lazy[nodo] = -1;
        }
        
        public int consulta(int i, int j){
            return consulta(1,1,N,i,j);
        }
        
        public int consulta(int nodo,int b,int e,int i,int j){
            if(i>e||j<b)
                return 0;
                
            if(b>=i && e<=j)
                return arbol[nodo];
                
            int mid = b+e>>1;
            
            if(lazy[nodo]>-1)
                propagar(nodo,b,mid,e);
            int q1 = consulta(nodo<<1,b,mid,i,j);
            int q2 = consulta(nodo<<1|1,mid+1,e,i,j);
            return q1+q2;
        }
    }
}