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;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline long long int rand(long long int x, long long int y) {
  ++y;
  return (rng() % (y - x)) + x;
}
long long int n, q;
string A;
struct node {
  int second, e, m;
  long long int v = 0, add = -1;
  node *l, *r;
  node(long long int _s, long long int _e) {
    second = _s, e = _e, m = (second + e) / 2;
    v = 0;
    add = -1;
    if (second != e) {
      l = new node(second, m);
      r = new node(m + 1, e);
    }
  }
  void update(long long int x, long long int y, long long int nv) {
    if (x > y) return;
    value();
    if (second == x && e == y) {
      add = nv;
      return;
    }
    if (x > m)
      r->update(x, y, nv);
    else if (y <= m)
      l->update(x, y, nv);
    else
      l->update(x, m, nv), r->update(m + 1, y, nv);
    v = l->value() + r->value();
  }
  long long int value() {
    if (add == -1) return v;
    v = add * ((long long int)(e - second + 1));
    if (second != e) {
      l->add = add;
      r->add = add;
    }
    add = -1;
    return v;
  }
  long long int rmq(long long int x, long long int y) {
    value();
    if (second == x && e == y) return v;
    if (x > m)
      return r->rmq(x, y);
    else if (y <= m)
      return l->rmq(x, y);
    else
      return l->rmq(x, m) + r->rmq(m + 1, y);
  }
} * seg[26];
int main() {
  cin >> n >> q >> A;
  for (long long int i = 0; i < 26; i++) seg[i] = new node(0, n - 1);
  for (long long int i = 0; i < n; i++) seg[A[i] - 'a']->update(i, i, 1);
  for (long long int i = 0; i < q; i++) {
    long long int a, b, op;
    cin >> a >> b >> op;
    --a, --b;
    if (op == 1) {
      long long int co = a;
      for (long long int j = 0; j < 26; j++) {
        long long int num = seg[j]->rmq(a, b);
        seg[j]->update(a, b, 0);
        seg[j]->update(co, co + num - 1, 1);
        co += num;
      }
    } else {
      long long int co = a;
      for (long long int j = 25; j >= 0; j--) {
        long long int num = seg[j]->rmq(a, b);
        seg[j]->update(a, b, 0);
        seg[j]->update(co, co + num - 1, 1);
        co += num;
      }
    }
  }
  for (long long int i = 0; i < n; i++) {
    for (long long int j = 0; j < 26; j++) {
      if (seg[j]->rmq(i, i) == 1) cout << (char)(j + 'a');
    }
  }
  cout << "\n";
}