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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.Reader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.BufferedReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Ruins He
 */
public class Main {
  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    InputReader in = new InputReader(inputStream);
    OutputWriter out = new OutputWriter(outputStream);
    TaskE solver = new TaskE();
    solver.solve(1, in, out);
    out.close();
  }

  static class TaskE {
    private static final int CHAR_SET_SIZE = 26;
    private int[][] tree;
    private int[] col;
    private int[] res;

    public void solve(int testNumber, InputReader in, OutputWriter out) {
      int n = in.nextInt();
      int m = in.nextInt();
      char[] s = in.next().toCharArray();
      tree = new int[n << 2][CHAR_SET_SIZE];
      col = new int[n << 2];
      res = new int[CHAR_SET_SIZE];
      Arrays.fill(col, -1);
      for (int i = 0; i < n; i++) {
        set(1, 1, n, i + 1, i + 1, s[i] - 'a');
      }
      for (int i = 0; i < m; i++) {
        int l = in.nextInt();
        int r = in.nextInt();
        int st = in.nextInt();
        if (st > 0) st = 1;
        else st = -1;
        Arrays.fill(res, 0);
        query(1, 1, n, l, r);
        for (int p = l, j = st > 0 ? 0 : CHAR_SET_SIZE - 1;
             j >= 0 && j < CHAR_SET_SIZE; p += res[j], j += st) {
          if (res[j] > 0) {
            set(1, 1, n, p, p + res[j] - 1, j);
          }
        }
      }

      for (int i = 1; i <= n; i++) {
        Arrays.fill(res, 0);
        query(1, 1, n, i, i);
        for (int j = 0; j < CHAR_SET_SIZE; j++) {
          if (res[j] != 0) {
            out.printf("%c", j + 'a');
            break;
          }
        }
      }
      out.println();
    }

    private void query(int k, int left, int right, int l, int r) {
      if (right < l || left > r) return;
      if (left >= l && right <= r) {
        for (int i = 0; i < CHAR_SET_SIZE; i++) res[i] += tree[k][i];
        return;
      }
      int mid = (left + right) >> 1;
      pushDown(k, left, mid, right);
      query(k << 1, left, mid, l, r);
      query(k << 1 | 1, mid + 1, right, l, r);
    }

    private void set(int k, int left, int right, int l, int r, int v) {
      if (right < l || left > r) return;
      if (left >= l && right <= r) {
        set(k, left, right, v);
        return;
      }
      int mid = (left + right) >> 1;
      pushDown(k, left, mid, right);
      set(k << 1, left, mid, l, r, v);
      set(k << 1 | 1, mid + 1, right, l, r, v);
      update(k);
    }

    private void update(int k) {
      for (int i = 0; i < CHAR_SET_SIZE; i++) tree[k][i] = tree[k << 1][i] + tree[k << 1 | 1][i];
    }

    private void pushDown(int k, int left, int mid, int right) {
      if (col[k] != -1) {
        set(k << 1, left, mid, col[k]);
        set(k << 1 | 1, mid + 1, right, col[k]);
        col[k] = -1;
      }
    }

    private void set(int k, int left, int right, int v) {
      for (int i = 0; i < CHAR_SET_SIZE; i++) tree[k][i] = 0;
      tree[k][v] = right - left + 1;
      col[k] = v;
    }

  }

  static class OutputWriter {
    private final PrintWriter writer;

    private OutputWriter(Writer writer, boolean autoFlush) {
      this.writer = new PrintWriter(new BufferedWriter(writer, 32767), autoFlush);
    }

    public OutputWriter(Writer writer) {
      this(writer, true);
    }

    public OutputWriter(OutputStream outputStream) {
      this(new OutputStreamWriter(outputStream), false);
    }

    public OutputWriter println() {
      writer.println();
      return this;
    }

    public OutputWriter printf(String format, Object... objects) {
      writer.printf(format, objects);
      return this;
    }

    public void close() {
      writer.close();
    }

  }

  static class InputReader {
    public final BufferedReader reader;
    public StringTokenizer tokenizer = null;

    public InputReader(Reader reader) {
      this.reader = new BufferedReader(reader, 32767);
    }

    public InputReader(InputStream inputStream) {
      this(new InputStreamReader(inputStream));
    }

    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());
    }

  }
}