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;
char s[100090];
struct node {
  int l, r, sum, flag;
  int mid() { return l + ((r - l) >> 1); }
  void fun(int x) {
    sum = (x - 1) * (r - l + 1);
    flag = x;
  }
};
struct segtree {
  node tree[100090 * 4];
  void relax(int rt) {
    int x = tree[rt].flag;
    tree[rt << 1].fun(x);
    tree[rt << 1 | 1].fun(x);
    tree[rt].flag = 0;
  }
  void build(int l, int r, int rt, int x) {
    tree[rt].l = l;
    tree[rt].r = r;
    tree[rt].flag = 0;
    if (l == r) {
      if (s[l] - 'a' == x)
        tree[rt].sum = 1;
      else
        tree[rt].sum = 0;
      return;
    }
    int mid = tree[rt].mid();
    build(l, mid, rt << 1, x);
    build(mid + 1, r, rt << 1 | 1, x);
    tree[rt].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum;
  }
  void update(int st, int ed, int rt, int x) {
    if (st > ed) return;
    int l = tree[rt].l, r = tree[rt].r;
    if (l >= st && r <= ed) {
      tree[rt].fun(x + 1);
      return;
    }
    if (tree[rt].flag) relax(rt);
    int mid = tree[rt].mid();
    if (mid >= st) update(st, ed, rt << 1, x);
    if (mid < ed) update(st, ed, rt << 1 | 1, x);
    tree[rt].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum;
  }
  int query(int st, int ed, int rt) {
    int l = tree[rt].l, r = tree[rt].r;
    if (l >= st && r <= ed) return tree[rt].sum;
    if (tree[rt].flag) relax(rt);
    int s1 = 0, s2 = 0, mid = tree[rt].mid();
    if (mid >= st) s1 = query(st, ed, rt << 1);
    if (mid < ed) s2 = query(st, ed, rt << 1 | 1);
    return s1 + s2;
  }
} seg[26];
void test(int n) {
  for (int(i) = 0; (i) < (4); (i)++) {
    for (int(j) = 1; (j) <= (n); (j)++) cout << seg[i].query(j, j, 1);
    cout << endl;
  }
  cout << endl;
}
int main() {
  int n, q, x, y, z, v[26], l, r;
  while (scanf("%d%d", &n, &q) != EOF) {
    scanf("%s", s + 1);
    for (int(i) = 0; (i) < (26); (i)++) seg[i].build(1, n, 1, i);
    while (q--) {
      scanf("%d%d%d", &x, &y, &z);
      for (int(i) = 0; (i) < (26); (i)++) v[i] = seg[i].query(x, y, 1);
      l = x;
      r = y;
      if (z == 1)
        for (int(i) = 0; (i) < (26); (i)++) {
          seg[i].update(x, y, 1, 0);
          seg[i].update(l, l + v[i] - 1, 1, 1);
          l += v[i];
        }
      else
        for (int(i) = 0; (i) < (26); (i)++) {
          seg[i].update(x, y, 1, 0);
          seg[i].update(r - v[i] + 1, r, 1, 1);
          r -= v[i];
        }
    }
    for (int i = 1; i <= n; i++)
      for (int(j) = 0; (j) < (26); (j)++)
        if (seg[j].query(i, i, 1)) printf("%c", 'a' + j);
    puts("");
  }
}