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;
template <class _T>
inline void rd(_T &_a) {
  int _f = 0, _ch = getchar();
  _a = 0;
  while (_ch < '0' || _ch > '9') {
    if (_ch == '-') _f = 1;
    _ch = getchar();
  }
  while (_ch >= '0' && _ch <= '9') _a = _a * 10 + _ch - '0', _ch = getchar();
  if (_f) _a = -_a;
}
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const int N = 1e5 + 5;
struct ssr {
  int s[26];
  void in() { memset(s, 0, sizeof s); }
} Ct;
struct tree {
  int l, r, lz;
  ssr s;
} t[N << 2];
int L, R, X;
char s[N];
ssr mg(ssr s1, ssr s2) {
  for (int i = 0; i < 26; i++) s1.s[i] += s2.s[i];
  return s1;
}
void Pu(int rt) { t[rt].s = mg(t[rt << 1].s, t[rt << 1 | 1].s); }
void Ch(int rt, int x) {
  t[rt].s.in();
  t[rt].s.s[t[rt].lz = x] = t[rt].r - t[rt].l + 1;
}
void Pd(int rt) {
  if (~t[rt].lz)
    Ch(rt << 1, t[rt].lz), Ch(rt << 1 | 1, t[rt].lz), t[rt].lz = -1;
}
void Bd(int l, int r, int rt = 1) {
  t[rt].l = l;
  t[rt].r = r;
  t[rt].lz = -1;
  if (l == r) return Ch(rt, s[l] - 'a');
  int m = l + r >> 1;
  Bd(l, m, rt << 1);
  Bd(m + 1, r, rt << 1 | 1);
  Pu(rt);
}
void Qy(int rt = 1) {
  if (L <= t[rt].l && t[rt].r <= R) {
    Ct = mg(Ct, t[rt].s);
    return;
  }
  Pd(rt);
  int m = t[rt].l + t[rt].r >> 1;
  if (L <= m) Qy(rt << 1);
  if (R > m) Qy(rt << 1 | 1);
}
void Ud(int rt = 1) {
  if (L <= t[rt].l && t[rt].r <= R) return Ch(rt, X);
  Pd(rt);
  int m = t[rt].l + t[rt].r >> 1;
  if (L <= m) Ud(rt << 1);
  if (R > m) Ud(rt << 1 | 1);
  Pu(rt);
}
void pqy(int l, int r) {
  L = l;
  R = r;
  Ct.in();
  Qy();
}
void pud(int l, int r, int x) {
  L = l;
  R = r;
  X = x;
  Ud();
}
void Pt(int rt = 1) {
  if (t[rt].l == t[rt].r) {
    printf("%c", t[rt].lz + 'a');
    return;
  }
  Pd(rt);
  Pt(rt << 1);
  Pt(rt << 1 | 1);
}
int main() {
  int n, m;
  rd(n);
  rd(m);
  scanf("%s", s + 1);
  Bd(1, n);
  for (int l, r, op, F, T, OP; m; m--) {
    rd(l);
    rd(r);
    rd(op);
    pqy(l, r);
    F = op ? 0 : 25;
    OP = op ? 1 : -1;
    T = 25 - F + OP;
    for (int i = F; i != T; i += OP)
      if (Ct.s[i]) pud(l, r, i), l += Ct.s[i];
  }
  Pt();
  return 0;
}