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 CPP):

Solution:
#include <bits/stdc++.h>
const int N = 1e5 + 10;
char input[N];
int ST[26][4 * N];
int set[26][4 * N];
int x[26][N] = {};
int calc[26];
int n, q;
inline int LC(int i) { return 2 * i + 1; }
inline int RC(int i) { return 2 * i + 2; }
void build(int L, int R, int i, int w);
void update(int L, int R, int i, int a, int b, int k, int w);
void renew(int L, int R, int i, int w);
int query(int L, int R, int i, int a, int b, int w);
int main() {
  while (scanf("%d%d", &n, &q) == 2) {
    int a, b, c;
    scanf("%s", input);
    for (int i = 0; i < n; i++) x[input[i] - 'a'][i] = 1;
    for (int i = 0; i < 26; i++) build(0, n - 1, 0, i);
    while (q--) {
      scanf("%d%d%d", &a, &b, &c);
      a--;
      b--;
      for (int i = 0; i < 26; i++) {
        calc[i] = query(0, n - 1, 0, a, b, i);
        update(0, n - 1, 0, a, b, 0, i);
      }
      if (c == 1) {
        int now = a;
        for (int i = 0; i < 26; i++) {
          update(0, n - 1, 0, a, a + calc[i] - 1, 1, i);
          a = a + calc[i];
        }
      } else {
        int now = a;
        for (int i = 25; i >= 0; i--) {
          update(0, n - 1, 0, a, a + calc[i] - 1, 1, i);
          a = a + calc[i];
        }
      }
    }
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < 26; j++) {
        if (query(0, n - 1, 0, i, i, j) == 1) {
          printf("%c", 'a' + j);
          break;
        }
      }
    }
    printf("\n");
  }
}
void build(int L, int R, int i, int w) {
  set[w][i] = 0;
  if (L == R) {
    ST[w][i] = x[w][L];
    return;
  }
  int M = (L + R) / 2;
  build(L, M, LC(i), w);
  build(M + 1, R, RC(i), w);
  ST[w][i] = ST[w][LC(i)] + ST[w][RC(i)];
  return;
}
void update(int L, int R, int i, int a, int b, int k, int w) {
  if (a > b) return;
  if (a <= L && b >= R) {
    if (L == R)
      ST[w][i] = k;
    else {
      set[w][i] = k + 1;
      ST[w][i] = k * (R - L + 1);
    }
    return;
  }
  if (a > R || b < L) return;
  int M = (L + R) / 2;
  if (set[w][i] != 0) renew(L, R, i, w);
  update(L, M, LC(i), a, b, k, w);
  update(M + 1, R, RC(i), a, b, k, w);
  ST[w][i] = ST[w][LC(i)] + ST[w][RC(i)];
}
void renew(int L, int R, int i, int w) {
  int k = -1;
  if (set[w][i] == 0) return;
  if (set[w][i] == 1)
    k = 0;
  else if (set[w][i] == 2)
    k = 1;
  set[w][i] = 0;
  if (L == R) return;
  int M = (L + R) / 2;
  update(L, M, LC(i), L, M, k, w);
  update(M + 1, R, RC(i), M + 1, R, k, w);
}
int query(int L, int R, int i, int a, int b, int w) {
  if (a <= L && b >= R) return ST[w][i];
  if (a > R || b < L) return 0;
  int M = (L + R) / 2;
  if (set[w][i] != 0) renew(L, R, i, w);
  return query(L, M, LC(i), a, b, w) + query(M + 1, R, RC(i), a, b, w);
}