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;
string st;
int n, q, i, j, l, r, k, kol[26], z;
class tr {
 public:
  int tree[400400], color[400400], num;
  void build(int v, int l, int r);
  void update(int v, int tl, int tr, int l, int r, int c);
  int get(int v, int tl, int tr, int l, int r);
  void push(int v, int l, int r);
};
void tr::build(int v, int l, int r) {
  int m;
  color[v] = -1;
  if (l == r)
    tree[v] = (st[l] == num);
  else {
    m = (l + r) / 2;
    build(v * 2, l, m);
    build(v * 2 + 1, m + 1, r);
    tree[v] = tree[v * 2] + tree[v * 2 + 1];
  }
}
void tr::update(int v, int tl, int tr, int l, int r, int c) {
  int tm;
  if (l > r) return;
  if (tl == l && tr == r) {
    color[v] = c;
    tree[v] = c * (r - l + 1);
  } else {
    tm = (tl + tr) / 2;
    push(v, tl, tr);
    update(v * 2, tl, tm, l, min(tm, r), c);
    update(v * 2 + 1, tm + 1, tr, max(tm + 1, l), r, c);
    tree[v] = tree[v * 2] + tree[v * 2 + 1];
  }
}
int tr::get(int v, int tl, int tr, int l, int r) {
  int tm;
  if (l > r) return 0;
  if (tl == l && tr == r)
    return tree[v];
  else {
    push(v, tl, tr);
    tm = (tl + tr) / 2;
    return get(v * 2, tl, tm, l, min(tm, r)) +
           get(v * 2 + 1, tm + 1, tr, max(tm + 1, l), r);
  }
}
void tr::push(int v, int l, int r) {
  int m;
  if (color[v] != -1) {
    m = (l + r) / 2;
    color[v * 2] = color[v * 2 + 1] = color[v];
    tree[v * 2] = (m - l + 1) * color[v];
    tree[v * 2 + 1] = (r - m) * color[v];
    color[v] = -1;
  }
}
tr ar[26];
int main() {
  cin >> n >> q;
  cin >> st;
  for (i = 0; i < 26; i++) {
    ar[i].num = 'a' + i;
    ar[i].build(1, 0, n - 1);
  }
  for (i = 0; i < q; i++) {
    cin >> l >> r >> k;
    for (j = 0; j < 26; j++) {
      kol[j] = ar[j].get(1, 0, n - 1, l - 1, r - 1);
      ar[j].update(1, 0, n - 1, l - 1, r - 1, 0);
    }
    if (k == 1) {
      for (j = 0; j < 26; j++) {
        ar[j].update(1, 0, n - 1, l - 1, l + kol[j] - 2, 1);
        l += kol[j];
      }
    } else {
      for (j = 25; j >= 0; j--) {
        ar[j].update(1, 0, n - 1, l - 1, l + kol[j] - 2, 1);
        l += kol[j];
      }
    }
  }
  for (z = 0; z < n; z++) {
    for (j = 0; j < 26; j++)
      if (ar[j].get(1, 0, n - 1, z, z)) {
        cout << char('a' + j);
      }
  }
  return 0;
}