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>
using namespace std;
const int N = 1e5 + 100;
char s[N];
struct SegmentTree {
  int val[N * 4];
  int flag[N * 4];
  void up(int rt) { val[rt] = val[rt << 1] + val[rt << 1 | 1]; }
  void build(int l, int r, int rt) {
    if (l == r) {
      val[rt] = 0;
      flag[rt] = -1;
      return;
    }
    int m = (l + r) >> 1;
    build(l, m, rt << 1);
    build(m + 1, r, rt << 1 | 1);
    up(rt);
  }
  void down(int rt, int m = 0) {
    if (flag[rt] != -1) {
      flag[rt << 1] = flag[rt];
      flag[rt << 1 | 1] = flag[rt];
      if (flag[rt] == 1) {
        val[rt << 1] = m - (m >> 1);
        val[rt << 1 | 1] = (m >> 1);
      } else {
        val[rt << 1] = 0;
        val[rt << 1 | 1] = 0;
      }
      flag[rt] = -1;
    }
  }
  void update(int p, int c, int l, int r, int rt) {
    if (l == r) {
      val[rt] = c;
      return;
    }
    down(rt, r - l + 1);
    int m = (l + r) >> 1;
    if (p <= m)
      update(p, c, l, m, rt << 1);
    else
      update(p, c, m + 1, r, rt << 1 | 1);
    up(rt);
  }
  void update(int L, int R, bool c, int l, int r, int rt) {
    if (L <= l && r <= R) {
      val[rt] = c ? (r - l + 1) : 0;
      flag[rt] = c;
      return;
    }
    down(rt, r - l + 1);
    int m = (l + r) >> 1;
    if (L <= m) update(L, R, c, l, m, rt << 1);
    if (R > m) update(L, R, c, m + 1, r, rt << 1 | 1);
    up(rt);
  }
  int query(int p, int l, int r, int rt) {
    if (l == r) {
      return val[rt];
    }
    down(rt, r - l + 1);
    int m = (l + r >> 1);
    if (p <= m)
      return query(p, l, m, rt << 1);
    else
      return query(p, m + 1, r, rt << 1 | 1);
  }
  int query(int L, int R, int l, int r, int rt) {
    if (L <= l && r <= R) {
      return val[rt];
    }
    down(rt, r - l + 1);
    int m = (l + r) >> 1;
    int ret = 0;
    if (L <= m) ret += query(L, R, l, m, rt << 1);
    if (R > m) ret += query(L, R, m + 1, r, rt << 1 | 1);
    return ret;
  }
} seg[26];
int main() {
  int n, q;
  scanf("%d %d", &n, &q);
  scanf("%s", s + 1);
  for (int i = 0; i < 26; i++) seg[i].build(1, n, 1);
  for (int i = 1; i <= n; i++) {
    int p = s[i] - 'a';
    seg[p].update(i, 1, 1, n, 1);
  }
  while (q--) {
    int l, r, t;
    scanf("%d %d %d", &l, &r, &t);
    int cnt[26];
    for (int i = 0; i < 26; i++) {
      cnt[i] = seg[i].query(l, r, 1, n, 1);
      if (cnt[i] > 0) {
        seg[i].update(l, r, 0, 1, n, 1);
      }
    }
    if (t == 1) {
      for (int i = 0; i < 26; l += cnt[i++]) {
        if (cnt[i] == 0) continue;
        seg[i].update(l, l + cnt[i] - 1, 1, 1, n, 1);
      }
    } else {
      for (int i = 25; i >= 0; l += cnt[i--]) {
        if (cnt[i] == 0) continue;
        seg[i].update(l, l + cnt[i] - 1, 1, 1, n, 1);
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < 26; j++) {
      if (seg[j].query(i, 1, n, 1)) {
        s[i] = 'a' + j;
        break;
      }
    }
  }
  s[n + 1] = 0;
  printf("%s\n", s + 1);
  return 0;
}