#include <bits/stdc++.h>
const int ms = 'z' - 'a' + 1;
struct node {
  node() { valid = false; }
  node(int a, int pos) {
    valid = true;
    memset(vals, 0, sizeof vals);
    elem = 1;
    vals[a] = 1;
    l = r = pos;
    lazy = 0;
  }
  node(node a, node b) {
    if (!a.valid)
      *this = b;
    else if (!b.valid)
      *this = a;
    else {
      valid = true;
      lazy = false;
      for (int i = 0; i < ms; i++) vals[i] = a.vals[i] + b.vals[i];
      elem = a.elem + b.elem;
      l = std::min(a.l, b.l);
      r = std::max(a.r, b.r);
    }
  }
  void add_lazy(node &a) {
    if (a.lazy) {
      lazy = a.lazy;
      for (int i = 0; i < ms; i++) vals[i] = a.vals[i];
      int rem;
      if (lazy == 1)
        rem = l - a.l;
      else
        rem = a.r - r;
      for (int i = 0; i < ms; i++) {
        int use = std::min(vals[i], rem);
        rem -= use;
        vals[i] -= use;
      }
      if (lazy == 1)
        rem = a.r - r;
      else
        rem = l - a.l;
      for (int i = ms - 1; i >= 0; i--) {
        int use = std::min(vals[i], rem);
        rem -= use;
        vals[i] -= use;
      }
    }
  }
  void inc_lazy() { lazy = false; }
  bool valid;
  int vals[ms];
  int elem, l, r;
  int lazy;
};
template <class i_t, class s_t, class lazy_cont = int>
class Segment_Tree {
 public:
  Segment_Tree(std::vector<s_t> _a) {
    a = _a;
    n = a.size();
    st.resize(4 * n);
    build(0, n - 1, 0);
  }
  i_t qry(int i, int j) { return qry(0, n - 1, i, j, 0); }
  void upd(int i, int j, lazy_cont val) { upd(0, n - 1, i, j, 0, val); }

 private:
  int left(int p) { return p + p + 1; }
  int right(int p) { return p + p + 2; }
  std::vector<s_t> a;
  std::vector<i_t> st;
  int n;
  void build(int l, int r, int ind) {
    if (l == r) {
      st[ind] = i_t(a[l], l);
      return;
    }
    int mid = (l + r) / 2;
    build(l, mid, left(ind));
    build(mid + 1, r, right(ind));
    st[ind] = i_t(st[left(ind)], st[right(ind)]);
  }
  void push(int l, int r, int ind) {
    if (!st[ind].lazy) return;
    if (l != r) {
      st[left(ind)].add_lazy(st[ind]);
      st[right(ind)].add_lazy(st[ind]);
    }
    st[ind].inc_lazy();
  }
  void upd(int l, int r, int i, int j, int ind, lazy_cont &val) {
    push(l, r, ind);
    if (r < i || l > j) return;
    if (l >= i && r <= j) {
      st[ind].add_lazy(val);
      push(l, r, ind);
    } else {
      int mid = (l + r) / 2;
      upd(l, mid, i, j, left(ind), val);
      upd(mid + 1, r, i, j, right(ind), val);
      st[ind] = i_t(st[left(ind)], st[right(ind)]);
    }
  }
  i_t qry(int l, int r, int i, int j, int ind) {
    int mid = (l + r) / 2;
    push(l, r, ind);
    if (r < i || l > j)
      return i_t();
    else if (l >= i && r <= j)
      return st[ind];
    return i_t(qry(l, mid, i, j, left(ind)), qry(mid + 1, r, i, j, right(ind)));
  }
};
int main() {
  int n, q;
  std::cin >> n >> q;
  std::string str;
  std::cin >> str;
  std::vector<int> a;
  for (int i = 0; i < n; i++) a.push_back(str[i] - 'a');
  Segment_Tree<node, int, node> tree(a);
  while (q--) {
    int l, r, v;
    std::cin >> l >> r >> v;
    l--;
    r--;
    node cont = tree.qry(l, r);
    if (v == 1)
      cont.lazy = 1;
    else
      cont.lazy = -1;
    tree.upd(l, r, cont);
  }
  for (int i = 0; i < n; i++) {
    node cont = tree.qry(i, i);
    for (int i = 0; i < ms; i++) {
      if (cont.vals[i]) std::cout << (char)('a' + i);
    }
  }
  std::cout << '\n';
}

### Prompt

Your challenge is to write a Cpp solution to the following 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>

### Response

```cpp
#include <bits/stdc++.h>
const int ms = 'z' - 'a' + 1;
struct node {
  node() { valid = false; }
  node(int a, int pos) {
    valid = true;
    memset(vals, 0, sizeof vals);
    elem = 1;
    vals[a] = 1;
    l = r = pos;
    lazy = 0;
  }
  node(node a, node b) {
    if (!a.valid)
      *this = b;
    else if (!b.valid)
      *this = a;
    else {
      valid = true;
      lazy = false;
      for (int i = 0; i < ms; i++) vals[i] = a.vals[i] + b.vals[i];
      elem = a.elem + b.elem;
      l = std::min(a.l, b.l);
      r = std::max(a.r, b.r);
    }
  }
  void add_lazy(node &a) {
    if (a.lazy) {
      lazy = a.lazy;
      for (int i = 0; i < ms; i++) vals[i] = a.vals[i];
      int rem;
      if (lazy == 1)
        rem = l - a.l;
      else
        rem = a.r - r;
      for (int i = 0; i < ms; i++) {
        int use = std::min(vals[i], rem);
        rem -= use;
        vals[i] -= use;
      }
      if (lazy == 1)
        rem = a.r - r;
      else
        rem = l - a.l;
      for (int i = ms - 1; i >= 0; i--) {
        int use = std::min(vals[i], rem);
        rem -= use;
        vals[i] -= use;
      }
    }
  }
  void inc_lazy() { lazy = false; }
  bool valid;
  int vals[ms];
  int elem, l, r;
  int lazy;
};
template <class i_t, class s_t, class lazy_cont = int>
class Segment_Tree {
 public:
  Segment_Tree(std::vector<s_t> _a) {
    a = _a;
    n = a.size();
    st.resize(4 * n);
    build(0, n - 1, 0);
  }
  i_t qry(int i, int j) { return qry(0, n - 1, i, j, 0); }
  void upd(int i, int j, lazy_cont val) { upd(0, n - 1, i, j, 0, val); }

 private:
  int left(int p) { return p + p + 1; }
  int right(int p) { return p + p + 2; }
  std::vector<s_t> a;
  std::vector<i_t> st;
  int n;
  void build(int l, int r, int ind) {
    if (l == r) {
      st[ind] = i_t(a[l], l);
      return;
    }
    int mid = (l + r) / 2;
    build(l, mid, left(ind));
    build(mid + 1, r, right(ind));
    st[ind] = i_t(st[left(ind)], st[right(ind)]);
  }
  void push(int l, int r, int ind) {
    if (!st[ind].lazy) return;
    if (l != r) {
      st[left(ind)].add_lazy(st[ind]);
      st[right(ind)].add_lazy(st[ind]);
    }
    st[ind].inc_lazy();
  }
  void upd(int l, int r, int i, int j, int ind, lazy_cont &val) {
    push(l, r, ind);
    if (r < i || l > j) return;
    if (l >= i && r <= j) {
      st[ind].add_lazy(val);
      push(l, r, ind);
    } else {
      int mid = (l + r) / 2;
      upd(l, mid, i, j, left(ind), val);
      upd(mid + 1, r, i, j, right(ind), val);
      st[ind] = i_t(st[left(ind)], st[right(ind)]);
    }
  }
  i_t qry(int l, int r, int i, int j, int ind) {
    int mid = (l + r) / 2;
    push(l, r, ind);
    if (r < i || l > j)
      return i_t();
    else if (l >= i && r <= j)
      return st[ind];
    return i_t(qry(l, mid, i, j, left(ind)), qry(mid + 1, r, i, j, right(ind)));
  }
};
int main() {
  int n, q;
  std::cin >> n >> q;
  std::string str;
  std::cin >> str;
  std::vector<int> a;
  for (int i = 0; i < n; i++) a.push_back(str[i] - 'a');
  Segment_Tree<node, int, node> tree(a);
  while (q--) {
    int l, r, v;
    std::cin >> l >> r >> v;
    l--;
    r--;
    node cont = tree.qry(l, r);
    if (v == 1)
      cont.lazy = 1;
    else
      cont.lazy = -1;
    tree.upd(l, r, cont);
  }
  for (int i = 0; i < n; i++) {
    node cont = tree.qry(i, i);
    for (int i = 0; i < ms; i++) {
      if (cont.vals[i]) std::cout << (char)('a' + i);
    }
  }
  std::cout << '\n';
}

```