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;
void shift(int tree[], int lazy[], int root, int start, int endd) {
  if (lazy[root] != -1) {
    int mid = start + endd >> 1;
    tree[2 * root + 1] = lazy[root] ? mid - start + 1 : 0;
    tree[2 * root + 2] = lazy[root] ? endd - mid : 0;
    lazy[2 * root + 1] = lazy[2 * root + 2] = lazy[root];
    lazy[root] = -1;
  }
}
void update(int tree[], int lazy[], int root, int start, int endd, int l, int r,
            const bool &v) {
  if (l > r) return;
  if (start == l && endd == r) {
    lazy[root] = v;
    tree[root] = v ? endd - start + 1 : 0;
    return;
  }
  shift(tree, lazy, root, start, endd);
  int mid = start + endd >> 1;
  update(tree, lazy, 2 * root + 1, start, mid, l, min(r, mid), v);
  update(tree, lazy, 2 * root + 2, mid + 1, endd, max(l, mid + 1), r, v);
  tree[root] = tree[2 * root + 1] + tree[2 * root + 2];
}
int get(int tree[], int lazy[], int root, int start, int endd, int l, int r) {
  if (l > r) return 0;
  if (start == l && endd == r) return tree[root];
  shift(tree, lazy, root, start, endd);
  int mid = start + endd >> 1;
  return get(tree, lazy, 2 * root + 1, start, mid, l, min(r, mid)) +
         get(tree, lazy, 2 * root + 2, mid + 1, endd, max(l, mid + 1), r);
}
const int max_n = 100 * 1000;
int tree[26][4 * max_n + 10], lazy[26][4 * max_n + 10];
int cnt[26];
int main() {
  int n, q;
  cin >> n >> q;
  string s;
  cin >> s;
  memset(tree, 0, sizeof tree);
  memset(lazy, -1, sizeof lazy);
  for (int i = 0; i < (n); i++)
    update(tree[s[i] - 'a'], lazy[s[i] - 'a'], 0, 0, n - 1, i, i, 1);
  while (q--) {
    int l, r, type;
    scanf("%d%d%d", &l, &r, &type);
    l--, r--;
    for (int i = 0; i < (26); i++)
      cnt[i] = get(tree[i], lazy[i], 0, 0, n - 1, l, r);
    for (int i = 0; i < (26); i++)
      update(tree[i], lazy[i], 0, 0, n - 1, l, r, 0);
    int cur = l;
    if (type)
      for (int i = 0; i < (26); i++) {
        update(tree[i], lazy[i], 0, 0, n - 1, cur, cur + cnt[i] - 1, 1);
        cur += cnt[i];
      }
    else
      for (int i = (25); i >= 0; i--) {
        update(tree[i], lazy[i], 0, 0, n - 1, cur, cur + cnt[i] - 1, 1);
        cur += cnt[i];
      }
  }
  string ans = "";
  for (int i = 0; i < (n); i++)
    for (int j = 0; j < (26); j++)
      if (get(tree[j], lazy[j], 0, 0, n - 1, i, i)) {
        ans += 'a' + j;
        break;
      }
  cout << ans << endl;
  return 0;
}