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;
int n, m, t[27];
char s[100005];
struct edge {
  int l, r, c[27], bj;
} e[100005 * 8];
void pushup(int v) {
  for (int i = 1; i <= 26; i++) e[v].c[i] = e[v * 2].c[i] + e[v * 2 + 1].c[i];
}
void pushdown(int v) {
  if (e[v].bj != -1) {
    int k = e[v].bj;
    memset(e[v * 2].c, 0, sizeof(e[v * 2].c));
    memset(e[v * 2 + 1].c, 0, sizeof(e[v * 2 + 1].c));
    e[v * 2].c[k] = e[v * 2].r - e[v * 2].l + 1;
    e[v * 2 + 1].c[k] = e[v * 2 + 1].r - e[v * 2 + 1].l + 1;
    e[v * 2].bj = e[v * 2 + 1].bj = k;
    e[v].bj = -1;
  }
}
void build(int v, int l, int r) {
  e[v].l = l, e[v].r = r;
  e[v].bj = -1;
  if (l == r) {
    e[v].c[s[l] - 'a' + 1] = 1;
    return;
  }
  int mid = (l + r) / 2;
  build(v * 2, l, mid);
  build(v * 2 + 1, mid + 1, r);
  pushup(v);
}
void add(int v, int l, int r, int opt) {
  if (e[v].l > r || l > e[v].r) return;
  if (l <= e[v].l && e[v].r <= r) {
    memset(e[v].c, 0, sizeof(e[v].c));
    e[v].c[opt] = e[v].r - e[v].l + 1;
    e[v].bj = opt;
    return;
  }
  pushdown(v);
  add(v * 2, l, r, opt);
  add(v * 2 + 1, l, r, opt);
  pushup(v);
}
void upd(int v, int l, int r) {
  if (e[v].l > r || l > e[v].r) return;
  if (l <= e[v].l && e[v].r <= r) {
    for (int i = 1; i <= 26; i++) {
      t[i] += e[v].c[i];
    }
    return;
  }
  pushdown(v);
  upd(v * 2, l, r);
  upd(v * 2 + 1, l, r);
  pushup(v);
}
void query(int v, int l, int r) {
  if (e[v].l > r || l > e[v].r) return;
  if (l <= e[v].l && e[v].r <= r) {
    for (int i = 1; i <= 26; i++)
      if (e[v].c[i]) printf("%c", char(i + 'a' - 1));
    return;
  }
  pushdown(v);
  query(v * 2, l, r);
  query(v * 2 + 1, l, r);
  pushup(v);
}
int main() {
  int x, y, l, opt;
  scanf("%d %d", &n, &m);
  scanf("%s", s + 1);
  build(1, 1, n);
  while (m--) {
    scanf("%d %d %d", &x, &y, &opt);
    upd(1, x, y);
    l = x;
    if (opt == 1) {
      for (int i = 1; i <= 26; i++) {
        if (t[i]) add(1, l, l + t[i] - 1, i), l += t[i], t[i] = 0;
      }
    } else {
      for (int i = 26; i >= 1; i--) {
        if (t[i]) add(1, l, l + t[i] - 1, i), l += t[i], t[i] = 0;
      }
    }
  }
  for (int i = 1; i <= n; i++) query(1, i, i);
  return 0;
}