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.*;
    import java.math.BigDecimal;
    import java.math.BigInteger;
    import java.util.*;

    public class Task2 {

        public static void main(String[] args) throws IOException {

            new Task2().solve();
        }

        int mod = 1000000007;

        PrintWriter out;

        int n;
        int m;

        ArrayList<Integer>[] g;

        void solve() throws IOException {

            //Reader in = new Reader("in.txt");
            //out = new PrintWriter( new BufferedWriter(new FileWriter("output.txt")) );
            Reader in = new Reader();
            PrintWriter out = new PrintWriter( new BufferedWriter(new OutputStreamWriter(System.out)) );

            //BufferedReader br = new BufferedReader( new FileReader("in.txt") );
            //BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );

            IntervalTree[] t = new IntervalTree[26];

            for (int i = 0; i < 26; i++)
                t[i] = new IntervalTree();

            int n = in.nextInt();
            int m = in.nextInt();

            String s = in.nextLine();

            for (int i = 0; i < s.length(); i++) {

                int ind = s.charAt(i) - 'a';
                t[ind].update(1, 0, n - 1, i, i, 1);
            }

            for (int i = 0; i < m; i++) {

//                if (1==1)
//                    continue;

                int l = in.nextInt()-1;
                int r = in.nextInt()-1;
                int k = 1-in.nextInt();

                int cur = l;
                if (k == 1)
                    cur = r;

                int[] cnt = new int[26];

                for (int j = 0; j < 26; j++)
                    cnt[j] = t[j].query(1, 0, n-1, l, r);

                for (int j = 0; j < 26; j++) {

                    if (cnt[j] == 0)
                        continue;

                    t[j].update(1, 0, n - 1, l, r, 0);

                    if (k == 0) {

                        t[j].update(1, 0, n-1, cur, cur+cnt[j]-1, 1);
                        cur += cnt[j];
                    }
                    else {

                        t[j].update(1, 0, n-1, cur-cnt[j]+1, cur, 1);
                        cur -= cnt[j];
                    }
                }
            }

            //System.err.println(t[3].query(1, 0, n-1, 8, 9));

            int[] res = new int[n];

            for (int i = 0; i < n; i++)
                for (int j = 0; j < 26; j++)
                    if (t[j].get(1, 0, n-1, i) == 1)
                        res[i] = j;


            for (int i = 0; i < n; i++)
                out.print((char)(res[i]+'a'));

            out.flush();
            out.close();
        }

        class IntervalTree {

            int[] t = new int[4*100000];
            int[] f = new int[4*100000];

            IntervalTree() {

                Arrays.fill(f, -1);
            }

            void push(int v, int tl, int tr) {

                if (f[v] == -1)
                    return;

                f[v*2] = f[v*2+1] = f[v];
                f[v] = -1;

                int tm = (tl+tr)/2;
                t[v*2] = (tm-tl+1)*f[v*2];
                t[v*2+1] = (tr-tm)*f[v*2+1];
            }

            void update(int v, int tl, int tr, int l, int r, int val) {

                if (l > r)
                    return;

                if (tl == l && tr == r) {

                    f[v] = val;
                    t[v] = val*(r-l+1);
                    return;
                }

                push(v, tl, tr);

                int tm = (tl+tr)/2;

                update(v*2, tl, tm, l, Math.min(tm, r), val);
                update(v*2+1, tm+1, tr, Math.max(l, tm+1), r, val);

                t[v] = t[v*2]+t[v*2+1];
            }

            int query(int v, int tl, int tr, int l, int r) {

                if (l > r)
                    return 0;

                if (tl == l && tr == r) {

                    return t[v];
                }

                push(v, tl, tr);

                int tm = (tl+tr)/2;

                return query(v*2, tl, tm, l, Math.min(tm ,r)) + query(v*2+1, tm+1, tr, Math.max(l, tm + 1), r);

            }

            int get(int v, int tl, int tr, int pos) {

                if (tl == tr)
                    return t[v];

                push(v, tl, tr);

                int tm = (tl+tr)/2;

                if (pos <= tm )
                    return get(v*2, tl, tm , pos);
                else
                    return get(v*2+1, tm+1, tr, pos);
            }

        }

        class Pair implements Comparable<Pair>{

            int a;
            int b;


            Pair(int a, int b) {

                this.a = a;
                this.b = b;
            }

            public int compareTo(Pair p) {

                if (a > p.a)
                    return 1;

                if (a < p.a)
                    return -1;

                if (b > p.b)
                    return 1;

                if (b < p.b)
                    return -1;

                return 0;
            }
        }

        class Reader {

            BufferedReader  br;
            StringTokenizer tok;

            Reader(String file) throws IOException {
                br = new BufferedReader( new FileReader(file) );
            }

            Reader() throws IOException {
                br = new BufferedReader( new InputStreamReader(System.in) );
            }

            String next() throws IOException {

                while (tok == null || !tok.hasMoreElements())
                    tok = new StringTokenizer(br.readLine());
                return tok.nextToken();
            }

            int nextInt() throws NumberFormatException, IOException {
                return Integer.valueOf(next());
            }

            long nextLong() throws NumberFormatException, IOException {
                return Long.valueOf(next());
            }

            double nextDouble() throws NumberFormatException, IOException {
                return Double.valueOf(next());
            }

            String nextLine() throws IOException {
                return br.readLine();
            }

        }

    }