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.util.*;

public class Main {

    void solve() throws IOException {
        int n = readInt();
        int q = readInt();

        char[] s = readString().toCharArray();
        int[] arr = new int[n];

        for (int i = 0; i < n; ++i) arr[i] = s[i] - 'a';
        SegmentTree[] sgt = new SegmentTree[26];
        for (int i = 0; i < 26; ++i) sgt[i] = new SegmentTree(n + 1);

        for (int i = 0; i < n; ++i) {
            sgt[arr[i]].update(i, i, 1);
        }
        while (q-- > 0) {
            int l = readInt() - 1;
            int r = readInt() - 1;
            int t = readInt();
            int sum = 0;
            if (t == 1) {
                for (int c = 0; c < 26; ++c) {
                    int count = sgt[c].getSegment(l, r);
                    int curLeft = l + sum;
                    int curRight = curLeft + count - 1;
                    sgt[c].update(l, r, 0);
                    sgt[c].update(curLeft, curRight, 1);
                    sum += count;
                }
            } else {
                for (int c = 25; c >= 0; --c) {
                    int count = sgt[c].getSegment(l, r);
                    int curLeft = l + sum;
                    int curRight = curLeft + count - 1;
                    sgt[c].update(l, r, 0);
                    sgt[c].update(curLeft, curRight, 1);
                    sum += count;
                }
            }
        }
        /*
        for (int c = 0; c < 26; c++)
        {
            out.println((char)(c + 'a') + " : " + sgt[c].getSegment(0, n - 1));
        }
        */
        for (int i = 0; i < n; ++i) {
            for (int c = 0; c < 26; ++c) {
                if (sgt[c].getSegment(i, i) > 0) {
                    out.print((char) ('a' + c));
                    break;
                }
                if (c == 25) out.print(" ");
            }
        }
    }

    class SegmentTree {
        int[] t;
        int[] pushes;
        int n, val, leftBorder, rightBorder, answer;

        SegmentTree(int n) {
            this.n = n;
            t = new int[4 * n];
            pushes = new int[4 * n];
            Arrays.fill(pushes, -1);
        }

        void update(int l, int r, int val) {
            this.val = val;
            this.leftBorder = l;
            this.rightBorder = r;
            lazyUpdate(1, 0, n - 1);
        }

        int getSegment(int l, int r) {
            this.leftBorder = l;
            this.rightBorder = r;
            answer = 0;
            get(1, 0, n - 1);
            return answer;
        }

        void get(int v, int tl, int tr) {
            push(v, tl, tr);
            if (tl >= leftBorder && tr <= rightBorder) {
                answer += t[v];
                return;
            }
            int mid = (tl + tr) >> 1;
            int left = v << 1;
            int right = left + 1;
            if (checkBorder(tl, mid))
                get(left, tl, mid);
            if (checkBorder(mid + 1, tr))
                get(right, mid + 1, tr);
        }
        boolean checkBorder(int tl, int tr){
            return tl <= rightBorder && tr >= leftBorder;
        }
        void lazyUpdate(int v, int tl, int tr) {
            push(v, tl, tr);
            if (tl >= leftBorder && tr <= rightBorder) {
                pushes[v] = val;
                push(v, tl, tr);
                return;
            }
            int mid = (tl + tr) / 2;
            int left = v * 2;
            int right = left + 1;
            if (tl <= rightBorder && mid >= leftBorder)
                lazyUpdate(left, tl, mid);
            if (tr >= leftBorder && mid + 1 <= rightBorder)
                lazyUpdate(right, mid + 1, tr);
            t[v] = get_answer(left, tl, mid) + get_answer(right, mid + 1, tr);
        }

        int get_answer(int v, int tl, int tr)
        {
            if (pushes[v] == -1)
                return t[v];
            return pushes[v] * (tr - tl + 1);
        }

        void push(int v, int tl, int tr) {
            if (pushes[v] == -1) return;
            t[v] = get_answer(v, tl, tr);
            if (tl != tr) {
                pushes[v * 2] = pushes[v];
                pushes[v * 2 + 1] = pushes[v];
            }
            pushes[v] = -1;
        }
    }

    class Vertex implements Comparable<Vertex> {
        int v, dist;

        public Vertex(int v, int dist) {
            this.v = v;
            this.dist = dist;
        }

        @Override
        public int compareTo(Vertex o) {
            return Integer.compare(this.dist, o.dist);
        }
    }

    int[][] steps = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    String fileName = "";
    int INF = Integer.MAX_VALUE / 2;
    long MODULO = 1000000007;
    private final static Random rnd = new Random();


    boolean checkBit(long mask, int bit) {
        return (mask & (1l << bit)) > 0;
    }

    ////////////////////////////////////////////////////////////
    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub
        new Main().run();
    }

    void run() throws NumberFormatException, IOException {
        solve();
        out.close();
    }

    ;

    BufferedReader in;
    PrintWriter out;

    StringTokenizer tok;
    String delim = " ";

    Main() throws FileNotFoundException {
        try {
            in = new BufferedReader(new FileReader("input.txt"));
            out = new PrintWriter("output.txt");
        } catch (Exception e) {
            if (fileName.isEmpty()) {
                in = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(System.out);
            } else {
                in = new BufferedReader(new FileReader(fileName + ".in"));
                out = new PrintWriter(fileName + ".out");
            }

        }
        tok = new StringTokenizer("");
    }

    String readLine() throws IOException {
        return in.readLine();
    }

    String readString() throws IOException {
        while (!tok.hasMoreTokens()) {
            String nextLine = readLine();
            if (null == nextLine) {
                return null;
            }

            tok = new StringTokenizer(nextLine);
        }
        return tok.nextToken(delim);
    }

    int readInt() throws NumberFormatException, IOException {
        return Integer.parseInt(readString());
    }

    long readLong() throws NumberFormatException, IOException {
        return Long.parseLong(readString());
    }

    int[] readIntArray(int n) throws NumberFormatException, IOException {
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) {
            a[i] = readInt();
        }
        return a;
    }

    double readDouble() throws NumberFormatException, IOException {
        return Double.parseDouble(readString());
    }
}