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 N = 1e5 + 5;
char s[N];
struct SegTree {
  int tree[N << 2], lazy[N << 2];
  void push_up(int rt) { tree[rt] = tree[rt << 1] + tree[rt << 1 | 1]; }
  void push_down(int rt, int l, int r) {
    if (lazy[rt] != -1) {
      int mid = (l + r) >> 1;
      tree[rt << 1] = (mid - l + 1) * lazy[rt];
      tree[rt << 1 | 1] = (r - mid) * lazy[rt];
      lazy[rt << 1] = lazy[rt << 1 | 1] = lazy[rt];
      lazy[rt] = -1;
    }
  }
  void build(int rt, int l, int r, char c) {
    tree[rt] = 0, lazy[rt] = -1;
    if (l == r) {
      tree[rt] = (s[l] == c);
      return;
    }
    int mid = (l + r) >> 1;
    build(rt << 1, l, mid, c);
    build(rt << 1 | 1, mid + 1, r, c);
    push_up(rt);
  }
  void update(int rt, int l, int r, int ql, int qr, int v) {
    if (ql <= l && qr >= r) {
      tree[rt] = (r - l + 1) * v;
      lazy[rt] = v;
      return;
    }
    push_down(rt, l, r);
    int mid = (l + r) >> 1;
    if (ql <= mid) update(rt << 1, l, mid, ql, qr, v);
    if (qr > mid) update(rt << 1 | 1, mid + 1, r, ql, qr, v);
    push_up(rt);
  }
  int query(int rt, int l, int r, int ql, int qr) {
    if (ql <= l && qr >= r) return tree[rt];
    push_down(rt, l, r);
    int res = 0, mid = (l + r) >> 1;
    if (ql <= mid) res += query(rt << 1, l, mid, ql, qr);
    if (qr > mid) res += query(rt << 1 | 1, mid + 1, r, ql, qr);
    push_up(rt);
    return res;
  }
  void print(int rt, int l, int r, char c) {
    if (l == r) {
      if (tree[rt]) s[l] = c;
      return;
    }
    push_down(rt, l, r);
    int mid = (l + r) >> 1;
    if (tree[rt]) print(rt << 1, l, mid, c), print(rt << 1 | 1, mid + 1, r, c);
    push_up(rt);
  }
} tr[30];
void print(int n) {
  for (int i = 0; i < 26; ++i) tr[i].print(1, 1, n, i + 'a');
  s[n + 1] = 0;
  puts(s + 1);
}
int main() {
  int n, q;
  scanf("%d%d", &n, &q);
  scanf("%s", s + 1);
  for (int i = 0; i < 26; ++i) tr[i].build(1, 1, n, 'a' + i);
  while (q--) {
    int l, r, k;
    scanf("%d%d%d", &l, &r, &k);
    int cot[30] = {0};
    for (int i = 0; i < 26; ++i) cot[i] = tr[i].query(1, 1, n, l, r);
    for (int i = 0; i < 26; ++i) tr[i].update(1, 1, n, l, r, 0);
    if (k == 0) {
      for (int i = 25; i >= 0; --i) {
        if (!cot[i]) continue;
        tr[i].update(1, 1, n, l, l + cot[i] - 1, 1);
        l += cot[i];
      }
    } else {
      for (int i = 0; i <= 25; ++i) {
        if (!cot[i]) continue;
        tr[i].update(1, 1, n, l, l + cot[i] - 1, 1);
        l += cot[i];
      }
    }
  }
  print(n);
}