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

public class E {

    private static final int ALPH_SIZE = 'z' - 'a' + 1;

    public static class Range {
        private int left;
        private int right;
        private int[] counts;
        private final boolean reversed;

        public Range(int left, int right, int[] counts, boolean reversed) {
            this.left = left;
            this.right = right;
            this.counts = counts;
            this.reversed = reversed;
        }

        public int getLeft() {
            return left;
        }

        public int getRight() {
            return right;
        }

        public void setLeft(int left) {
            this.left = left;
        }

        public void setRight(int right) {
            this.right = right;
        }

        public int[] getCounts() {
            return counts;
        }

        public boolean isReversed() {
            return reversed;
        }

        public String print() {
            StringBuilder builder = new StringBuilder();
            if (isReversed()) {
                for (int i = ALPH_SIZE - 1; i >= 0; i--) {
                    for (int k = 0; k < counts[i]; ++k) {
                        builder.append((char)('a' + i));
                    }
                }
            } else {
                for (int i = 0; i < ALPH_SIZE; i++) {
                    for (int k = 0; k < counts[i]; ++k) {
                        builder.append((char)('a' + i));
                    }
                }
            }
            return builder.toString();
        }

        @Override
        public String toString() {
            return "[" + left + ", " + right + "] " + (reversed ? 1 : 0) + " " + print();
        }
    }

    public static TreeSet<Range> construct(String input) {
        TreeSet<Range> rangeSet = new TreeSet<>((x, y) -> Integer.compare(x.getLeft(), y.getLeft()));
        for (int i = 0; i < input.length(); i++) {
            int[] counts = new int[ALPH_SIZE];
            counts[input.charAt(i) - 'a']++;
            Range range = new Range(i, i + 1, counts, false);
            rangeSet.add(range);
        }
        return rangeSet;
    }

    public static void sort(TreeSet<Range> rangeSet, int left, int right, boolean reversed) {
        Range destRange = new Range(left, right, new int[ALPH_SIZE], reversed);
        Range sourceRange = rangeSet.floor(destRange);
        while (sourceRange != null && sourceRange.getLeft() < destRange.getRight()) {
            int[] destCounts = destRange.getCounts();
            int[] sourceCounts = sourceRange.getCounts();
            rangeSet.remove(sourceRange);
            boolean isSourceToLeft = sourceRange.getLeft() < destRange.getLeft();
            boolean isSourceToRight = sourceRange.getRight() > destRange.getRight();
            if (isSourceToLeft || isSourceToRight) {
                if (isSourceToLeft && isSourceToRight) {
                    int toTake = destRange.getLeft() - sourceRange.getLeft();
                    int[] leftCounts = new int[ALPH_SIZE];
                    takeCounts(leftCounts, sourceCounts, toTake, !sourceRange.isReversed());
                    Range leftRange = new Range(sourceRange.getLeft(), destRange.getLeft(), leftCounts, sourceRange.isReversed());
                    rangeSet.add(leftRange);

                    toTake = sourceRange.getRight() - destRange.getRight();
                    int[] rightCounts = new int[ALPH_SIZE];
                    takeCounts(rightCounts, sourceCounts, toTake, sourceRange.isReversed());
                    Range rightRange = new Range(destRange.getRight(), sourceRange.getRight(), rightCounts, sourceRange.isReversed());
                    rangeSet.add(rightRange);

                    destRange = new Range(left, right, sourceCounts, reversed);
                    break;
                } else if (isSourceToLeft) {
                    int toTake = sourceRange.getRight() - destRange.getLeft();
                    takeCounts(destCounts, sourceCounts, toTake, sourceRange.isReversed());
                    Range leftSourceRange = new Range(sourceRange.getLeft(), destRange.getLeft(), sourceCounts, sourceRange.isReversed());
                    rangeSet.add(leftSourceRange);
                } else {
                    int toTake = destRange.getRight() - sourceRange.getLeft();
                    takeCounts(destCounts, sourceCounts, toTake, !sourceRange.isReversed());
                    Range rightSourceRange = new Range(destRange.getRight(), sourceRange.getRight(), sourceCounts, sourceRange.isReversed());
                    rangeSet.add(rightSourceRange);
                }
            } else {
                takeCounts(destCounts, sourceCounts, sourceRange.getRight() - sourceRange.getLeft(), true);
            }

            sourceRange = rangeSet.higher(sourceRange);
        }
        rangeSet.add(destRange);
    }

    private static void takeCounts(int[] destCounts, int[] sourceCounts, int toTake, boolean fromStart) {
        int index = 0;
        int delta = 1;
        if (!fromStart) {
            index = ALPH_SIZE - 1;
            delta = -1;
        }
        while (toTake > 0) {
            int takeNow = Math.min(sourceCounts[index], toTake);
            destCounts[index] += takeNow;
            sourceCounts[index] -= takeNow;
            toTake -= takeNow;
            index += delta;
        }
    }

    public static String print(TreeSet<Range> rangeSet) {
        StringBuilder builder = new StringBuilder();
        for (Range range : rangeSet) {
            builder.append(range.print());
        }
        return builder.toString();
    }

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int q = s.nextInt();
        String input = s.next();
        TreeSet<Range> ranges =  construct(input);
        for (int i = 0; i < q; i++) {
            int left = s.nextInt() - 1;
            int right = s.nextInt();
            boolean reverse = s.nextInt() == 0;
            sort(ranges, left, right, reverse);
        }
        String answer = print(ranges);
        System.out.print(answer);
    }
}