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 + 10, MOD = 1e9 + 7, INF = 1e9 + 10, SQ = 550, LOG = 25;
int n, m, x1, x2, d, z, t, y2, maxi, mini, ptr, l, r, dp[130][N << 2], tmp[130],
    lazy[N << 2], sz[N << 2], x, y, k;
string s;
vector<long long> v;
void shift(long long pos, long long lch, long long rch) {
  if (lazy[pos] == 0) return;
  for (int i = 'a'; i <= 'z'; i++) dp[i][lch] = dp[i][rch] = 0;
  if (lazy[pos] == 1) {
    lazy[lch] = lazy[rch] = 1;
    long long now[130], siz = sz[lch];
    for (int i = 'a'; i <= 'z'; i++) now[i] = dp[i][pos];
    for (int i = 'a'; i <= 'z'; i++) {
      if (now[i] > siz) {
        dp[i][lch] += siz;
        now[i] -= siz;
        siz = 0;
      } else {
        siz -= now[i];
        dp[i][lch] += now[i];
        now[i] = 0;
      }
    }
    for (int i = 'a'; i <= 'z'; i++) {
      dp[i][rch] += now[i];
    }
  } else if (lazy[pos] == 2) {
    lazy[lch] = lazy[rch] = 2;
    long long now[130], siz = sz[lch];
    for (int i = 'a'; i <= 'z'; i++) now[i] = dp[i][pos];
    for (int i = 'z'; i >= 'a'; i--) {
      if (now[i] > siz) {
        dp[i][lch] += siz;
        now[i] -= siz;
        siz = 0;
      } else {
        siz -= now[i];
        dp[i][lch] += now[i];
        now[i] = 0;
      }
    }
    for (int i = 'a'; i <= 'z'; i++) {
      dp[i][rch] += now[i];
    }
  }
  lazy[pos] = 0;
}
void bld(long long b, long long e, long long pos) {
  long long mid = b + e >> 1, lch = pos << 1, rch = lch + 1;
  sz[pos] = e - b;
  if (b == e - 1) {
    dp[s[b]][pos]++;
    return;
  }
  bld(b, mid, lch);
  bld(mid, e, rch);
  for (int i = 'a'; i <= 'z'; i++) dp[i][pos] = dp[i][lch] + dp[i][rch];
}
void _get(long long b, long long e, long long pos) {
  long long mid = b + e >> 1, lch = pos << 1, rch = lch + 1;
  if (b >= y || e <= x) return;
  if (x <= b && e <= y) {
    for (int i = 'a'; i <= 'z'; i++) tmp[i] += dp[i][pos];
    return;
  }
  shift(pos, lch, rch);
  _get(b, mid, lch);
  _get(mid, e, rch);
}
void upd(long long b, long long e, long long pos) {
  long long mid = b + e >> 1, lch = pos << 1, rch = lch + 1;
  if (b >= y || e <= x) return;
  if (x <= b && e <= y) {
    lazy[pos] = z;
    for (int i = 'a'; i <= 'z'; i++) dp[i][pos] = 0;
    long long siz = sz[pos];
    if (z == 1) {
      for (int i = 'a'; i <= 'z'; i++) {
        if (tmp[i] > siz) {
          dp[i][pos] += siz;
          tmp[i] -= siz;
          siz = 0;
        } else {
          siz -= tmp[i];
          dp[i][pos] += tmp[i];
          tmp[i] = 0;
        }
      }
    } else {
      for (int i = 'z'; i >= 'a'; i--) {
        if (tmp[i] > siz) {
          dp[i][pos] += siz;
          tmp[i] -= siz;
          siz = 0;
        } else {
          siz -= tmp[i];
          dp[i][pos] += tmp[i];
          tmp[i] = 0;
        }
      }
    }
    return;
  }
  shift(pos, lch, rch);
  upd(b, mid, lch);
  upd(mid, e, rch);
  for (int i = 'a'; i <= 'z'; i++) dp[i][pos] = dp[i][lch] + dp[i][rch];
}
void _go(long long b, long long e, long long pos) {
  long long mid = b + e >> 1, lch = pos << 1, rch = lch + 1;
  if (b == e - 1) {
    for (int i = 'a'; i <= 'z'; i++) {
      if (dp[i][pos]) {
        cout << (char)i;
      }
    }
    return;
  }
  shift(pos, lch, rch);
  _go(b, mid, lch);
  _go(mid, e, rch);
  for (int i = 'a'; i <= 'z'; i++) dp[i][pos] = dp[i][lch] + dp[i][rch];
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> m >> s;
  bld(0, n, 1);
  while (m--) {
    cin >> x >> y >> z;
    x--;
    z++;
    z = 3 - z;
    for (int i = 'a'; i <= 'z'; i++) tmp[i] = 0;
    _get(0, n, 1);
    upd(0, n, 1);
  }
  _go(0, n, 1);
}