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 mod = (int)1e9 + 7;
int n, q;
string s;
int t[27][400400];
int add[27][400400];
void build(int v, int tl, int tr) {
  for (int i = 0; i < 26; ++i) {
    add[i][v] = -1;
  }
  if (tl == tr) {
    t[s[tl] - 'a'][v] = 1;
    return;
  }
  int mid = (tl + tr) >> 1;
  build(v + v, tl, mid);
  build(v + v + 1, mid + 1, tr);
  for (int i = 0; i < 26; ++i) {
    t[i][v] = t[i][v + v] + t[i][v + v + 1];
  }
}
void push(int v, int type, int tl, int tr) {
  if (add[type][v] != -1) {
    int mid = (tl + tr) >> 1;
    t[type][v + v] = (mid - tl + 1) * add[type][v];
    t[type][v + v + 1] = (tr - mid) * add[type][v];
    add[type][v + v] = add[type][v + v + 1] = add[type][v];
    add[type][v] = -1;
  }
}
void update(int v, int tl, int tr, int l, int r, int type, int val) {
  if (tl > r || tr < l) return;
  if (l <= tl && tr <= r) {
    t[type][v] = (tr - tl + 1) * val;
    add[type][v] = val;
    return;
  }
  push(v, type, tl, tr);
  int mid = (tl + tr) >> 1;
  update(v + v, tl, mid, l, r, type, val);
  update(v + v + 1, mid + 1, tr, l, r, type, val);
  t[type][v] = t[type][v + v] + t[type][v + v + 1];
}
int get(int v, int tl, int tr, int l, int r, int type) {
  if (tl > r || tr < l) return 0;
  if (l <= tl && tr <= r) return t[type][v];
  push(v, type, tl, tr);
  int mid = (tl + tr) >> 1;
  return get(v + v, tl, mid, l, r, type) +
         get(v + v + 1, mid + 1, tr, l, r, type);
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  cin >> n >> q;
  cin >> s;
  build(1, 0, n - 1);
  while (q--) {
    int l, r, k;
    cin >> l >> r >> k;
    l--, r--;
    if (k) {
      int curL = l;
      for (int i = 0; i < 26; ++i) {
        int cnt = get(1, 0, n - 1, l, r, i);
        if (cnt) {
          update(1, 0, n - 1, l, r, i, 0);
          update(1, 0, n - 1, curL, curL + cnt - 1, i, 1);
          curL = curL + cnt;
        }
      }
    } else {
      int curR = r;
      for (int i = 0; i < 26; ++i) {
        int cnt = get(1, 0, n - 1, l, r, i);
        if (cnt) {
          update(1, 0, n - 1, l, r, i, 0);
          update(1, 0, n - 1, curR - cnt + 1, curR, i, 1);
          curR = curR - cnt;
        }
      }
    }
  }
  for (int i = 0; i < n; ++i) {
    int was = 0;
    for (int j = 0; j < 26; ++j) {
      if (get(1, 0, n - 1, i, i, j) == 1) {
        s[i] = j + 'a';
      }
    }
  }
  cout << s << endl;
}