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:
//package cf312;

import java.io.*;
import java.util.StringTokenizer;
import java.util.function.BiFunction;
import java.util.function.Function;
import java.util.function.IntBinaryOperator;
import java.util.function.IntUnaryOperator;

public class ETemplateTest {
    static boolean CONSTRUCTIVE = false;
    static long BIG = (long) 2e9;
    static int n;

    public static void solve(Reader sc, PrintWriter out) {
        n = sc.nextInt();
        int q = sc.nextInt();
        char[] arr = sc.next().toCharArray();
        SegTree[] roots = new SegTree[26];
        for (int j = 0; j < 26; j++) {
            char c = (char) ('a' + j);
            roots[j] = new SegTree(i -> c == arr[i] ? 1 : 0, Integer::sum, (f, g) -> g);
        }

        for (int i = 0; i < q; i++) {
            int l = sc.nextInt() - 1;
            int r = sc.nextInt() - 1;
            boolean increasing = sc.nextInt() == 1;

            int index = l;
            if (increasing) {
                for (int let = 0; let < 26; let++) {
                    int count = roots[let].getRange(l, r);
                    if (count > 0) {
                        roots[let].setRange(l, r, 0);
                        roots[let].setRange(index, index + count - 1, 1);
                    }
                    index += count;
                }
            } else {
                for (int let = 25; let >= 0; let--) {
                    int count = roots[let].getRange(l, r);
                    if (count > 0) {
                        roots[let].setRange(l, r, 0);
                        roots[let].setRange(index, index + count - 1, 1);
                    }
                    index += count;
                }
            }
        }
        print(n, roots, out);
    }

    static void print(int n, SegTree[] roots, PrintWriter out) {
        char[] arr = new char[n];
        for (int i = 0; i < n; i++) {
            for (int c = 0; c < 26; c++) {
                if (roots[c].get(i) > 0) {
                    arr[i] = (char) ('a' + c);
                    break;
                }
            }
        }
        out.println(new String(arr));
    }

    public static void main(String[] args) throws IOException {
        Reader in = null;
        PrintWriter out = null;
        for (String arg : args) {
            if (arg.startsWith("input")) {
                in = new Reader(arg);
            } else if (arg.startsWith("output")) {
                out = new PrintWriter(new FileWriter(arg));
            }
        }
        if (in == null) in = new Reader();
        if (out == null) out = new PrintWriter(new OutputStreamWriter(System.out));

        solve(in, out);

        out.flush();
    }

    static class Tester {
        public static void main(String[] args) throws IOException {
            Validator validator = new Validator();

            System.out.println("SAMPLE TESTS:");
            File currentDir = new File(".");
            long before;
            long after;
            for (File inputFile : currentDir.listFiles()) {
                if (!inputFile.getName().matches("input[0-9]")) continue;
                int number = Integer.parseInt(inputFile.getName().substring(5));
                System.out.printf("Test %d: \n", number);

                before = System.nanoTime();
                String outputFileName = "output" + inputFile.getName().substring(5);
                ETemplateTest.main(new String[]{inputFile.getName(), outputFileName});
                after = System.nanoTime();

                File outputFile = new File("output" + number);
                if (!outputFile.exists()) {
                    throw new IllegalStateException("Missing output file " + outputFile);
                }

                // TODO if verifier is implemented, remove this
                if (CONSTRUCTIVE) {
                    System.out.println("INPUT:");
                    printFile(inputFile);
                    System.out.printf("\nOUTPUT: (%d milliseconds)\n", (after - before) / 1000000L);
                    printFile(outputFile);
                    continue;
                }

                if (validator.validate(inputFile, outputFile)) {
                    System.out.printf("OK (%d milliseconds)\n", (after - before) / 1000000L);
                } else {
                    System.out.println("FAILED");
                    System.out.println("\nInput: ");
                    printFile(inputFile);
                    System.out.println("\nIncorrect Output: ");
                    printFile(outputFile);
                    return;
                }
            }
            System.out.println("\n-----------------\n");

            File sightTestInput = new File("input-sight");
            if (sightTestInput.exists()) {
                System.out.println("Running sight test... Input:");
                printFile(sightTestInput);
                before = System.nanoTime();
                System.out.println("\nOutput: ");
                ETemplateTest.main(new String[]{"input-sight"});
                after = System.nanoTime();
                System.out.printf("(%d milliseconds)\n", (after - before) / 1000000L);
                System.out.println("\n-----------------\n");
            }

            File bigTestInput = new File("input-big");
            if (bigTestInput.exists()) {
                System.out.println("Running big test...");
                before = System.nanoTime();
                ETemplateTest.main(new String[]{"input-big"});
                after = System.nanoTime();
                System.out.printf("(%d milliseconds)\n", (after - before) / 1000000L);
            }
        }

        static void printFile(File file) throws FileNotFoundException {
            BufferedReader reader = new BufferedReader(new FileReader(file));
            reader.lines().forEach(System.out::println);
        }
    }

    static class Validator {
        boolean validate(File inputFile, File outputFile) throws IOException {
            int number = Integer.parseInt(inputFile.getName().substring(5));
            File expectedOutputFile = new File("expected-output" + number);
            if (CONSTRUCTIVE || !expectedOutputFile.exists()) {
                return validateManual(inputFile, outputFile);
            }
            return areSame(outputFile, expectedOutputFile);
        }

        private boolean validateManual(File inputFile, File outputFile) throws IOException {
            // OPTION 1: validate against naive solution
//            Naive.main(new String[] {inputFile.getName()})


            // OPTION 2: Validate output against input (typically for constructive problems)
            Reader inputReader = new Reader(inputFile.getName());
            Reader outputReader = new Reader(outputFile.getName());

            // TODO implement manual validation

            throw new IllegalStateException("Missing expected output file");
        }

        private boolean areSame(File file1, File file2) throws IOException {
            BufferedReader reader1 = new BufferedReader(new FileReader(file1));
            BufferedReader reader2 = new BufferedReader(new FileReader(file2));

            String line1;
            while ((line1 = reader1.readLine()) != null) {
                String line2 = reader2.readLine();
                if (line2 == null) line2 = ""; // ok if one has an extra newline
                if (!line1.trim().equals(line2.trim())) {
                    return false;
                }
            }
            String line2;
            while ((line2 = reader2.readLine()) != null) {
                if (!line2.trim().isEmpty()) {
                    return false;
                }
            }
            return true;
        }

    }

    static class Naive {
        public static void solveNaive(Reader in, FileWriter out) {

        }

        public static void main(String[] args) throws IOException {
            Reader in = null;
            PrintWriter out = null;
            for (String arg : args) {
                if (arg.startsWith("input")) {
                    in = new Reader(arg);
                } else if (arg.startsWith("output")) {
                    out = new PrintWriter(new FileWriter(arg));
                }
            }
            if (in == null) in = new Reader();
            if (out == null) out = new PrintWriter(new OutputStreamWriter(System.out));

            int tests = in.nextInt();
            for (int t = 0; t < tests; t++) {
                solve(in, out);
            }

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

    // return highest in that still returns true
    // invariant:
    // -    indicator(min) = true
    // -    indicator(max+1) = false
    static int binarySearch(int min, int max, Function<Integer, Boolean> indicator) {
        int a = min;
        int b = max;
        while (a != b) {
            int mid = (a % 2 != b % 2) ? 1 + (a + b) / 2 : (a + b) / 2;
            if (indicator.apply(mid)) {
                a = mid;
            } else {
                b = mid - 1;
            }
        }
        return a;
    }

    static class SegTree {
        final int[] vals;
        final IntBinaryOperator[] lazyUpdates;
        final Integer[] lazyAssignments;
        final IntUnaryOperator initialAssignment;
        final IntBinaryOperator accumulator;
        final BiFunction<IntBinaryOperator, IntBinaryOperator, IntBinaryOperator> compositionRule;

        SegTree(
                IntUnaryOperator initialAssignment,
                IntBinaryOperator accumulator,
                BiFunction<IntBinaryOperator, IntBinaryOperator, IntBinaryOperator> compositionRule) {
            vals = new int[2 * n];
            lazyUpdates = new IntBinaryOperator[2 * n];
            lazyAssignments = new Integer[2*n];
            this.initialAssignment = initialAssignment;
            this.accumulator = accumulator;
            this.compositionRule = compositionRule;
            construct(1, 0, n - 1);
        }

        private void construct(int v, int a, int b) {
            if (a == b) {
                vals[v] = initialAssignment.applyAsInt(a);

            } else {
                int mid = (a + b) / 2;
                construct(v+1, a, mid);
                construct(v+2*(mid-a+1), mid + 1, b);
                vals[v] = accumulator.applyAsInt(vals[v+1], vals[v+2*(mid-a+1)]);
            }
        }

        void update(int index, IntBinaryOperator updateFunc) {
            updateRange(index, index, updateFunc);
        }

        void updateRange(int l, int r, IntBinaryOperator updateFunction) {
            updateRange(1, 0, n - 1, l, r, updateFunction);
        }

        void setRange(int l, int r, int set) {
            setRange(1, 0, n-1, l, r, set);
        }

        private void setRange(int v, int a, int b, int l, int r, int set) {
            // enforce
            if (l < a || r > b) {
                throw new IllegalStateException(
                        String.format("[%d %d] out of range of [%d %d]", l, r, a, b));
            }

            if (l == a && r == b) {
                if (b > a) {
                    lazyAssignments[v] = set;
                }
                vals[v] = set * (r-l+1);
            } else {
                int mid = (a + b) / 2;
                if (b > a && lazyAssignments[v] != null) {
                    int lazyUpdate = lazyAssignments[v];
                    lazyAssignments[v] = null;
                    // apply existing update to everything outside of [l, r]
                    if (l > a) setRange(v, a, b, a, l - 1, lazyUpdate);
                    if (r < b) setRange(v, a, b, r + 1, b, lazyUpdate);
                }

                if (l <= mid) {
                    setRange(v+1, a, mid, l, Math.min(r, mid), set);
                }
                if (r > mid) {
                    setRange(v+2*(mid-a+1), mid + 1, b, Math.max(mid + 1, l), r, set);
                }
                vals[v] = accumulator.applyAsInt(vals[v+1], vals[v+2*(mid-a+1)]);
            }
        }

        private void updateRange(int v, int a, int b, int l, int r, IntBinaryOperator updateFunction) {
            // enforce
            if (l < a || r > b) {
                throw new IllegalStateException(
                        String.format("[%d %d] out of range of [%d %d]", l, r, a, b));
            }

            if (l == a && r == b) {
                if (b > a) {
                    lazyUpdates[v] = (lazyUpdates[v] == null)
                            ? updateFunction
                            : compositionRule.apply(lazyUpdates[v], updateFunction);
                }
                vals[v] = updateFunction.applyAsInt(vals[v], r - l + 1);
            } else {
                IntBinaryOperator composed;

                int mid = (a + b) / 2;
                if (b > a && lazyUpdates[v] != null) {
                    IntBinaryOperator lazyUpdate = lazyUpdates[v];
                    lazyUpdates[v] = null;
                    // apply existing update to everything outside of [l, r]
                    if (l > a) updateRange(v, a, b, a, l - 1, lazyUpdate);
                    if (r < b) updateRange(v, a, b, r + 1, b, lazyUpdate);
                    composed = compositionRule.apply(lazyUpdate, updateFunction);
                } else {
                    composed = updateFunction;
                }

                if (l <= mid) {
                    updateRange(v+1, a, mid, l, Math.min(r, mid), composed);
                }
                if (r > mid) {
                    updateRange(v+2*(mid-a+1), mid + 1, b, Math.max(mid + 1, l), r, composed);
                }
                vals[v] = accumulator.applyAsInt(vals[v+1], vals[v+2*(mid-a+1)]);
            }
        }

        int get(int index) {
            return getRange(index, index);
        }

        int getRange(int l, int r) {
            return getRange(1, 0, n - 1, l, r);
        }

        private int getRange(int v, int a, int b, int l, int r) {
            if (r < l) throw new IllegalStateException();
            if (l < a || r > b) throw new IllegalStateException();

            int val = vals[v];

            if (l == a && r == b) {
                return val;
            }

            int mid = (a + b) / 2;

            if (lazyAssignments[v] != null) {
                return lazyAssignments[v] * (r-l+1);
            }
            if (lazyUpdates[v] != null) {
                updateRange(v+1, a, mid, a, mid, lazyUpdates[v]);
                updateRange(v+2*(mid-a+1), mid + 1, b, mid + 1, b, lazyUpdates[v]);
                lazyUpdates[v] = null;
            }

            Integer ret = null;
            if (l <= mid) {
                ret = getRange(v+1, a, mid, l, Math.min(mid, r));
            }
            if (r >= mid + 1) {
                if (ret == null) ret = getRange(v+2*(mid-a+1), mid + 1, b, Math.max(l, mid + 1), r);
                else ret = accumulator.applyAsInt(ret, getRange(v+2*(mid-a+1), mid + 1, b, Math.max(l, mid + 1), r));
            }
            return ret;
        }

    }

    static long pair(int x, int y) {
        return x * BIG + y;
    }

    static int x(long pair) {
        return (int) (pair / BIG);
    }

    static int y(long pair) {
        return (int) (pair % BIG);
    }

    static class Reader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public Reader() {
            reader = new BufferedReader(new InputStreamReader(System.in), 32768);
            tokenizer = null;
        }

        public Reader(String fileName) throws FileNotFoundException {
            reader = new BufferedReader(new FileReader(fileName));
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }
    }
}