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 maxn = 100005;
int n, q;
char s[maxn];
int lazy[26][4 * maxn], ans[26][4 * maxn], lo[26][4 * maxn], hi[26][4 * maxn];
void build(int node, int ind, int l, int r) {
  lo[node][ind] = l, hi[node][ind] = r;
  if (lo[node][ind] == hi[node][ind]) {
    ans[node][ind] = (s[l] - 'a') == node ? 1 : 0;
    lazy[node][ind] = -1;
    return;
  }
  int mid = l + (r - l) / 2;
  build(node, ind * 2, l, mid);
  build(node, ind * 2 + 1, mid + 1, r);
  ans[node][ind] = ans[node][ind * 2] + ans[node][ind * 2 + 1];
  lazy[node][ind] = -1;
}
void upd(int node, int ind) {
  ans[node][ind] = lazy[node][ind] * (hi[node][ind] - lo[node][ind] + 1);
}
void prop(int node, int ind) {
  if (lazy[node][ind] != -1) {
    lazy[node][ind * 2] = lazy[node][ind];
    lazy[node][ind * 2 + 1] = lazy[node][ind];
    upd(node, ind * 2);
    upd(node, ind * 2 + 1);
    lazy[node][ind] = -1;
  }
}
void update(int node, int ind, int l, int r, int c) {
  if (r < lo[node][ind] || l > hi[node][ind]) return;
  if (l <= lo[node][ind] && hi[node][ind] <= r) {
    lazy[node][ind] = c;
    ans[node][ind] = c * (hi[node][ind] - lo[node][ind] + 1);
    return;
  }
  prop(node, ind);
  update(node, ind * 2, l, r, c);
  update(node, ind * 2 + 1, l, r, c);
  ans[node][ind] = ans[node][ind * 2] + ans[node][ind * 2 + 1];
}
int query(int node, int ind, int l, int r) {
  if (r < lo[node][ind] || l > hi[node][ind]) return 0;
  if (l <= lo[node][ind] && hi[node][ind] <= r) {
    return ans[node][ind];
  }
  prop(node, ind);
  return query(node, ind * 2, l, r) + query(node, ind * 2 + 1, l, r);
}
int f[26];
int main() {
  cin >> n >> q;
  scanf("%s", s);
  for (int i = 0; i < 26; ++i) {
    build(i, 1, 0, n - 1);
  }
  while (q--) {
    int l, r, k;
    scanf("%d %d %d", &l, &r, &k);
    --l, --r;
    for (int i = 0; i < 26; ++i) {
      f[i] = query(i, 1, l, r);
      update(i, 1, l, r, 0);
    }
    if (k == 1) {
      int ind = l;
      for (int i = 0; i < 26; ++i) {
        if (f[i]) {
          update(i, 1, ind, ind + f[i] - 1, 1);
          ind += f[i];
        }
      }
    } else {
      int ind = l;
      for (int i = 25; i >= 0; --i) {
        if (f[i]) {
          update(i, 1, ind, ind + f[i] - 1, 1);
          ind += f[i];
        }
      }
    }
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < 26; ++j) {
      if (query(j, 1, i, i)) {
        printf("%c", (char)(j + 'a'));
        break;
      }
    }
  }
}