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 = 1e5;
int tree[MAXN * 4], sum[MAXN * 4];
int val[MAXN * 4];
int n;
void build(const string &s, char c, int v = 0, int vl = 0, int vr = n) {
  if (vr - vl == 1) {
    tree[v] = (s[vl] > c);
    val[v] = -1;
    return;
  }
  int vm = (vl + vr) / 2;
  build(s, c, v * 2 + 1, vl, vm);
  build(s, c, v * 2 + 2, vm, vr);
  tree[v] = tree[v * 2 + 1] + tree[v * 2 + 2];
  val[v] = -1;
}
inline void push(int v, int vl, int vr) {
  if (val[v] != -1) {
    tree[v] = val[v] * (vr - vl);
    if (vr - vl != 1) {
      val[v * 2 + 1] = val[v];
      val[v * 2 + 2] = val[v];
    }
    val[v] = -1;
  }
}
void update(int l, int r, int x, int v = 0, int vl = 0, int vr = n) {
  push(v, vl, vr);
  if (l <= vl && vr <= r) {
    val[v] = x;
    push(v, vl, vr);
    return;
  }
  if (r <= vl || vr <= l) {
    return;
  }
  int vm = (vl + vr) / 2;
  update(l, r, x, v * 2 + 1, vl, vm);
  update(l, r, x, v * 2 + 2, vm, vr);
  tree[v] = tree[v * 2 + 1] + tree[v * 2 + 2];
}
int get_sum(int l, int r, int v = 0, int vl = 0, int vr = n) {
  push(v, vl, vr);
  if (l <= vl && vr <= r) {
    return tree[v];
  }
  if (r <= vl || vr <= l) {
    return 0;
  }
  int vm = (vl + vr) / 2;
  return get_sum(l, r, v * 2 + 1, vl, vm) + get_sum(l, r, v * 2 + 2, vm, vr);
}
char ans[MAXN];
void get_ans(char c, int v = 0, int vl = 0, int vr = n) {
  push(v, vl, vr);
  if (sum[v] + tree[v] == vr - vl) {
    return;
  }
  if (vr - vl == 1) {
    ans[vl] = c;
    sum[v] = 1;
    return;
  }
  int vm = (vl + vr) / 2;
  get_ans(c, v * 2 + 1, vl, vm);
  get_ans(c, v * 2 + 2, vm, vr);
  sum[v] = sum[v * 2 + 1] + sum[v * 2 + 2];
}
void print(int v = 0, int vl = 0, int vr = n) {
  push(v, vl, vr);
  if (vr - vl == 1) {
    cout << tree[v];
    return;
  }
  int vm = (vl + vr) / 2;
  print(v * 2 + 1, vl, vm);
  print(v * 2 + 2, vm, vr);
}
struct query {
  int left, right, type;
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  memset(val, 255, sizeof(val));
  int m;
  cin >> n >> m;
  string s;
  cin >> s;
  vector<query> q(m);
  for (auto &[l, r, t] : q) {
    cin >> l >> r >> t;
    l--;
  }
  for (int c = 0; c < 26; c++) {
    build(s, c + 'a');
    for (auto &[left, right, type] : q) {
      int s = get_sum(left, right);
      if (s == 0 || s == right - left) {
        continue;
      }
      if (type == 1) {
        update(left, right - s, 0);
        update(right - s, right, 1);
      } else {
        update(left, left + s, 1);
        update(left + s, right, 0);
      }
    }
    get_ans(c + 'a');
  }
  for (int i = 0; i < n; i++) {
    cout << ans[i];
  }
  cout << '\n';
  return 0;
}