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.FileReader;
import java.io.FileWriter;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import static java.lang.Math.*;

public class code0 {
    private static boolean oj = System.getProperty("ONLINE_JUDGE") != null;
    private static Reader in;
    private static PrintWriter out;
    ////////////////////////////////////////////////////////////////////////////////////////////////////
    private static int min(int... a){int min=a[0]; for(int i:a) min=Math.min(min, i); return min;}
    private static int max(int... a){int max=a[0]; for(int i:a) max=Math.max(max, i); return max;}
    private static long min(long... a){long min=a[0]; for(long i:a)min=Math.min(min, i); return min;}
    private static long max(long... a){long max=a[0]; for(long i:a)max=Math.max(max, i); return max;}
    private static String strm(String str, long m) {
        String ans="";
        while(m>0) {
            if(m%2==1) ans=ans.concat(str);
            str=str.concat(str); m>>=1;
        } return ans;
    }
    private static long mod(long a, long mod) {long res = a%mod; return res>=0 ? res : res+mod;}
    private static int mod(int a, int mod) {int res = a%mod; return res>=0 ? res : res+mod;}
    private static long modpow(long x, int n, int mod) {
        long res = 1;
        for (long p = x; n > 0; n >>= 1, p = mod((mod(p, mod)*mod(p, mod)),  mod)) {
            if ((n & 1) != 0) res = mod(mod(res, mod) * mod(p, mod), mod);
        }
        return res;
    }
    private static long gcd(long a, long b) {return b == 0 ? Math.abs(a) : gcd(b, a % b);}
    private static int gcd(int a, int b) {return b == 0 ? Math.abs(a) : gcd(b, a % b);}
    private static long gcd(long... a) {long gcd=a[0]; for(long x:a) gcd=gcd(gcd, x); return gcd;}
    private static int gcd(int... a) {int gcd=a[0]; for(int x:a) gcd=gcd(gcd, x); return gcd;}
    private static long lcm(long a, long b) {return Math.abs(a / gcd(a, b) * b);}
    private static boolean isEven(int num) {return ((num&1) == 0);}
    private static boolean isOdd(int num) {return !isEven(num);}
    private static boolean isEven(long num) {return ((num&1) == 0);}
    private static boolean isOdd(long num) {return !isEven(num);}
    private static class Pair {
        public int x, y;
        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
        @Override
        public boolean equals(Object obj) {
            if (obj == this) return true;
            if (!(obj instanceof Pair)) return false;
            Pair pair = (Pair)obj;
            return this.x == pair.x && this.y == pair.y;
        }
        @Override
        public String toString() {
            return ("(" + this.x + "," + this.y + ")");
        }
        @Override
        public int hashCode() {
            return (this.x+" "+this.y).hashCode();
        }
    }
    private static class Triplet {
        public int x, y, z;
        public Triplet(int x, int y, int z) {
            this.x = x;
            this.y = y;
            this.z = z;
        }
        @Override
        public boolean equals(Object obj) {
            if (obj == this) return true;
            if (!(obj instanceof Triplet)) return false;
            Triplet triplet = (Triplet)obj;
            return this.x == triplet.x && this.y == triplet.y && this.z == triplet.z;
        }
        @Override
        public String toString() {
            return ("(" + this.x + "," + this.y + "," + this.z + ")");
        }
        @Override
        public int hashCode() {
            return (this.x+" "+this.y+" "+this.z).hashCode();
        }
    }
    ////////////////////////////////////////////////////////////////////////////////////////////////////
    static class Reader {
        private BufferedReader br;
        private StringTokenizer token;
        private Reader(FileReader obj) {
            br = new BufferedReader(obj, 32768);
            token = null;
        }
        private Reader() {
            br = new BufferedReader(new InputStreamReader(System.in), 32768);
            token = null;
        }
        private String next() {
            while(token == null || !token.hasMoreTokens()) {
                try {
                    token = new StringTokenizer(br.readLine());
                } catch (Exception e) {e.printStackTrace();}
            } return token.nextToken();
        }
        private String nextLine() {
            String str="";
            try {
                str = br.readLine();
            } catch (Exception e) {e.printStackTrace();}
            return str;
        }
        private int nextInt() {return Integer.parseInt(next());}
        private long nextLong() {return Long.parseLong(next());}
        private double nextDouble() {return Double.parseDouble(next());}
        private long[] nextLongArr(int n) {
            long[] arr = new long[n]; for(int i=0; i<n; i++) arr[i] = nextLong(); return arr;
        }
        private int[] nextIntArr(int n) {
            int[] arr = new int[n]; for(int i=0; i<n; i++) arr[i] = nextInt(); return arr;
        }
    }
    ////////////////////////////////////////////////////////////////////////////////////////////////////
    private static final int mod = 1_000_000_007;
    private static int n;
    private static String str;
    private static char[] ans;
    static class SegmentTree {
        private int[][] st;
        private int[][] lazy;
        private SegmentTree() {
            int x = (int)ceil(log(n)/log(2));
            int size = (1<<(x+1)) - 1;
            st = new int[size][26];
            lazy = new int[size][26];
            buildTree(0, 0, n-1);
        }
        private int getMid(int sts, int ste) {
            return (sts+ste)>>1;
        }
        private void buildTree(int sti, int sts, int ste) {
            if (sts == ste) {
                st[sti][str.charAt(sts) - 'a'] = 1;
                for(int j=0;j<26;j++) lazy[sti][j] = -1;
                return;
            }
            int mid = getMid(sts, ste);
            buildTree(2*sti+1, sts, mid);
            buildTree(2*sti+2, mid+1, ste);
            for (int i=0; i<26; i++) {
                lazy[sti][i] = -1;
                st[sti][i] = st[2*sti+1][i] + st[2*sti+2][i];
            }
            return;
        }
        private int getSum(int sti, int sts, int ste, int qs, int qe, int k) {
            if (lazy[sti][k] != -1) {
                st[sti][k] = (ste-sts+1)*lazy[sti][k];
                if (sts != ste) {
                    lazy[2*sti+1][k] = lazy[sti][k];
                    lazy[2*sti+2][k] = lazy[sti][k];
                }
                lazy[sti][k] = -1;
            }
            if (qs<=sts && ste<=qe) return st[sti][k];
            if (qs>ste || qe<sts) return 0;
            int mid = getMid(sts, ste);
            return getSum(2*sti+1, sts, mid, qs, qe, k) + getSum(2*sti+2, mid+1, ste, qs, qe, k);
        }
        private void update(int sti, int sts, int ste, int qs, int qe, int k, int val) {
            if (lazy[sti][k] != -1) {
                st[sti][k] = (ste-sts+1)*lazy[sti][k];
                if (sts != ste) {
                    lazy[2*sti+1][k] = lazy[sti][k];
                    lazy[2*sti+2][k] = lazy[sti][k];
                }
                lazy[sti][k] = -1;
            }
            if (qs>ste || qe<sts) return;
            if (qs<=sts && ste<=qe) {
                st[sti][k] = (ste-sts+1)*val;
                if (sts != ste) {
                    lazy[2*sti+1][k] = val;
                    lazy[2*sti+2][k] = val;
                }
                return;
            }
            int mid = getMid(sts, ste);
            update(2*sti+1, sts, mid, qs, qe, k, val);
            update(2*sti+2, mid+1, ste, qs, qe, k, val);
            st[sti][k] = st[2*sti+1][k] + st[2*sti+2][k];
            return;
        }
        private void getString(int sti, int sts, int ste, int k) {
            if (lazy[sti][k] != -1) {
                st[sti][k] = (ste-sts+1)*lazy[sti][k];
                if (sts != ste) {
                    lazy[2*sti+1][k] = lazy[sti][k];
                    lazy[2*sti+2][k] = lazy[sti][k];
                }
                lazy[sti][k] = -1;
            }
            if (st[sti][k] == 0) return;
            if (sts == ste) {
                ans[sts] = (char)(k+97);
                // out.println(k+65);
                return;
            }
            int mid = getMid(sts, ste);
            getString(2*sti+1, sts, mid, k);
            getString(2*sti+2, mid+1, ste, k);
            return;
        }
    }
    private static void solve() throws Exception {
        n = in.nextInt(); int q = in.nextInt();
        str = in.nextLine();
        int[] count;
        SegmentTree st = new SegmentTree();
        while (q-->0) {
            int qs = in.nextInt()-1, qe = in.nextInt()-1, asc = in.nextInt();
            count = new int[26];
            for (int i=0; i<26; i++) {
                count[i] = st.getSum(0, 0, n-1, qs, qe, i);
            }
            int start = qs;
            if (asc == 0) start = qe;
            for (int i=0; i<26; i++) {
                if (count[i] == 0) continue;
                st.update(0, 0, n-1, qs, qe, i, 0);
                if (asc == 1) {
                    st.update(0, 0, n-1, start, start+count[i]-1, i, 1);
                    start = start+count[i];
                } else {
                    st.update(0, 0, n-1, start-count[i]+1, start, i, 1);
                    start = start-count[i];
                }
            }
        }
        ans = new char[n];
        for (int i=0; i<26; i++) {
            st.getString(0, 0, n-1, i);
        }
        out.printf("%s\n", String.valueOf(ans));
    }
    private static void run() throws Exception {
        // in = new Reader();
        // in = new Reader(new FileReader("input.txt"));
        // out = new PrintWriter(new FileWriter("output.txt"));
        in = oj ? new Reader() : new Reader(new FileReader("/home/raiden/Desktop/input.txt"));
        out = new PrintWriter(System.out);
        // out = new PrintWriter(new FileWriter("/home/raiden/Desktop/output.txt"));
        long ti = System.currentTimeMillis();
        solve(); out.flush();
        if (!oj) System.out.println("\n"+(System.currentTimeMillis()-ti)+"ms");
    }
    public static void main(String[] args) throws Exception {run();}
}