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 = 1e+5 + 100;
struct tree {
  int t[4 * maxn];
  int add[4 * maxn];
  tree() {
    for (int i = 0; i < 4 * maxn; ++i) add[i] = -1;
  }
  void push(int v, int L, int R) {
    if (add[v] != -1) {
      if (L != R) {
        add[2 * v + 1] = add[v];
        add[2 * v + 2] = add[v];
      }
      t[v] = (R - L + 1) * add[v];
      add[v] = -1;
    }
  }
  void recalc(int v) { t[v] = t[2 * v + 1] + t[2 * v + 2]; }
  void build(int v, int L, int R, vector<int> &arr, int x) {
    if (L == R) {
      if (x == arr[L]) t[v] = 1;
      return;
    }
    int middle = (L + R) >> 1;
    build(2 * v + 1, L, middle, arr, x);
    build(2 * v + 2, middle + 1, R, arr, x);
    recalc(v);
  }
  int query(int v, int L, int R, int l, int r) {
    push(v, l, r);
    if (r < L || R < l) return 0;
    if (L <= l && r <= R) {
      return t[v];
    }
    int middle = (l + r) >> 1;
    int q1 = query(2 * v + 1, L, R, l, middle);
    int q2 = query(2 * v + 2, L, R, middle + 1, r);
    return q1 + q2;
  }
  void update(int v, int L, int R, int l, int r, int val) {
    push(v, l, r);
    if (r < L || R < l) return;
    if (L <= l && r <= R) {
      add[v] = val;
      push(v, l, r);
      return;
    }
    int middle = (l + r) >> 1;
    update(2 * v + 1, L, R, l, middle, val);
    update(2 * v + 2, L, R, middle + 1, r, val);
    recalc(v);
  }
};
tree t[26];
int main() {
  ios_base::sync_with_stdio(false);
  int n, q;
  cin >> n >> q;
  string s;
  cin >> s;
  vector<int> ss;
  for (int iter = 0; iter < ((int)s.length()); ++iter)
    ss.push_back(s[iter] - 'a');
  for (int iter = 0; iter < 26; ++iter)
    t[iter].build(0, 0, ((int)s.length()) - 1, ss, iter);
  for (int iter = 0; iter < q; ++iter) {
    int i, j, k;
    cin >> i >> j >> k;
    i--, j--;
    vector<int> curval(26);
    int all = j - i + 1;
    for (int let = 0; let < 26 && all; let++) {
      curval[let] = t[let].query(0, i, j, 0, ((int)s.length()) - 1);
      all -= curval[let];
      if (curval[let]) t[let].update(0, i, j, 0, ((int)s.length()) - 1, 0);
    }
    if (!k) {
      int pointer = i;
      for (int let = 25; let >= 0; --let) {
        if (curval[let]) {
          t[let].update(0, pointer, pointer + curval[let] - 1, 0,
                        ((int)s.length()) - 1, 1);
          pointer += curval[let];
        }
      }
    } else {
      int pointer = i;
      for (int let = 0; let < 26; ++let) {
        if (curval[let]) {
          t[let].update(0, pointer, pointer + curval[let] - 1, 0,
                        ((int)s.length()) - 1, 1);
          pointer += curval[let];
        }
      }
    }
  }
  for (int iter = 0; iter < n; ++iter) {
    for (int let = 0; let < 26; ++let) {
      int val = t[let].query(0, iter, iter, 0, ((int)s.length()) - 1);
      if (val) {
        s[iter] = 'a' + let;
        break;
      }
    }
  }
  cout << s << "\n";
  return 0;
}