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>
const int MAXN = 110000;
const int MAXS = 26;
struct SegmentTree {
  struct Node {
    int l, r, val[MAXS], cov;
    void operator=(const Node& rhs) {
      for (int i = 0; i < 26; i++) val[i] = rhs.val[i];
    }
    Node operator+(const Node& rhs) const {
      Node sum;
      for (int i = 0; i < 26; i++) sum.val[i] = val[i] + rhs.val[i];
      return sum;
    }
    int value() {
      for (int i = 0; i < 26; i++)
        if (val[i]) return i;
      return 0;
    }
  } tr[MAXN << 2];
  void pushup(int root) { tr[root] = tr[(root << 1)] + tr[(root << 1 | 1)]; }
  void cover(int root, int k) {
    for (int i = 0; i < 26; i++) tr[root].val[i] = 0;
    tr[root].val[k] = tr[root].r - tr[root].l + 1;
    tr[root].cov = k;
  }
  void pushdown(int root) {
    if (tr[root].cov == -1) return;
    cover((root << 1), tr[root].cov);
    cover((root << 1 | 1), tr[root].cov);
    tr[root].cov = -1;
  }
  void build(int root, int l, int r, int* a) {
    tr[root].l = l;
    tr[root].r = r;
    tr[root].cov = -1;
    if (l == r) {
      for (int i = 0; i < 26; i++) tr[root].val[i] = 0;
      tr[root].val[a[l]] = 1;
      return;
    }
    int mid = l + r >> 1;
    build((root << 1), l, mid, a);
    build((root << 1 | 1), mid + 1, r, a);
    pushup(root);
  }
  void update(int root, int l, int r, int k) {
    if (tr[root].l > r || tr[root].r < l) return;
    if (l <= tr[root].l && tr[root].r <= r) {
      cover(root, k);
      return;
    }
    pushdown(root);
    update((root << 1), l, r, k);
    update((root << 1 | 1), l, r, k);
    pushup(root);
  }
  Node query(int root, int l, int r) {
    if (tr[root].l > r || tr[root].r < l) return Node();
    if (l <= tr[root].l && tr[root].r <= r) return tr[root];
    pushdown(root);
    return query((root << 1), l, r) + query((root << 1 | 1), l, r);
  }
  void ndorder(int l, int r) {
    Node tmp = query(1, l, r);
    for (int i = 0, p = l; i < 26; i++)
      update(1, p, p + tmp.val[i] - 1, i), p += tmp.val[i];
  }
  void niorder(int l, int r) {
    Node tmp = query(1, l, r);
    for (int i = 25, p = l; i >= 0; i--)
      update(1, p, p + tmp.val[i] - 1, i), p += tmp.val[i];
  }
  void getans(int root) {
    if (tr[root].l == tr[root].r) {
      putchar(tr[root].value() + 'a');
      return;
    }
    pushdown(root);
    getans((root << 1));
    getans((root << 1 | 1));
  }
} st;
char s[MAXN];
int a[MAXN];
int main() {
  int n, q;
  scanf("%d%d%s", &n, &q, s + 1);
  for (int i = 1; i <= n; i++) a[i] = s[i] - 'a';
  st.build(1, 1, n, a);
  while (q--) {
    int l, r, k;
    scanf("%d%d%d", &l, &r, &k);
    if (k == 1)
      st.ndorder(l, r);
    else
      st.niorder(l, r);
  }
  st.getans(1);
  return 0;
}