#include <bits/stdc++.h>
using namespace std;
struct RTC {};
struct Tree {
  typedef struct _node {
    int y, cnt;
    bool sorted_node, rev;
    int c_in_subtree[26], c_in_node[26];
    _node *l, *r;
    _node(char value = 0)
        : y((rand() << 16) ^ rand()), cnt(1), l(nullptr), r(nullptr) {
      memset(c_in_subtree, 0, sizeof(c_in_subtree));
      memset(c_in_node, 0, sizeof(c_in_node));
      sorted_node = rev = false;
      if (value != 0) {
        c_in_subtree[value - 'a'] = 1;
        c_in_node[value - 'a'] = 1;
      }
    }
    ~_node() {
      delete l;
      delete r;
    }
    void recalc() {
      cnt = 0;
      for (int i = 0; i < (26); i++) {
        c_in_subtree[i] = c_in_node[i];
        cnt += c_in_node[i];
      }
      if (l) {
        for (int i = 0; i < (26); i++) c_in_subtree[i] += l->c_in_subtree[i];
        cnt += l->cnt;
      }
      if (r) {
        for (int i = 0; i < (26); i++) c_in_subtree[i] += r->c_in_subtree[i];
        cnt += r->cnt;
      }
    }
    void push_sort(bool re = false) {
      sorted_node = true;
      rev = re;
      cnt = 0;
      for (int i = 0; i < (26); i++) {
        c_in_node[i] = c_in_subtree[i];
        cnt += c_in_subtree[i];
      }
      l = r = nullptr;
    }
  } * node;
  Tree() : root(nullptr) {}
  ~Tree() { delete root; }
  pair<node, node> split_node(node t, int pos) {
    node TL = new _node(), TR = new _node();
    for (int i = 0; i < (26); i++) TR->c_in_node[i] = t->c_in_node[i];
    if (t->rev) {
      TL->rev = true;
      TR->rev = true;
      int take = pos;
      for (int i = 25; i >= 0 && take > 0; i--) {
        if (TR->c_in_node[i] > 0) {
          int tmp = min(take, TR->c_in_node[i]);
          TL->c_in_node[i] = tmp;
          TR->c_in_node[i] -= tmp;
          take -= tmp;
        } else {
          TL->c_in_node[i] = 0;
        }
      }
    } else {
      int take = pos;
      for (int i = 0; i < 26 && take > 0; i++) {
        if (TR->c_in_node[i] > 0) {
          int tmp = min(take, TR->c_in_node[i]);
          TL->c_in_node[i] = tmp;
          TR->c_in_node[i] -= tmp;
          take -= tmp;
        } else {
          TL->c_in_node[i] = 0;
        }
      }
    }
    TL->recalc();
    TR->recalc();
    for (int i = 0; i < (26); i++)
      assert((TL->c_in_node[i]) + (TR->c_in_node[i]) == (t->c_in_node[i]));
    if ((TL->cnt) == 0) TL = nullptr;
    if ((TR->cnt) == 0) TR = nullptr;
    return make_pair(TL, TR);
  }
  node root;
  void split(node t, int x, node &L, node &R) {
    if (t == nullptr) {
      L = R = nullptr;
      return;
    }
    int cnt_in_node = accumulate(t->c_in_node, t->c_in_node + 26, 0);
    int a = cnt(t->l), b = a + cnt_in_node - 1;
    if (cnt_in_node > 1 && a <= x && x <= b) {
      pair<node, node> tmp = split_node(t, x - a);
      L = merge(t->l, tmp.first);
      R = merge(tmp.second, t->r);
    } else {
      int curIndex = cnt(t->l) + cnt_in_node;
      if (curIndex <= x) {
        split(t->r, x - curIndex, t->r, R);
        L = t;
      } else {
        split(t->l, x, L, t->l);
        R = t;
      }
      t->recalc();
    }
  }
  node merge(node L, node R) {
    if (L == nullptr) return R;
    if (R == nullptr) return L;
    if (L->y > R->y) {
      L->r = merge(L->r, R);
      L->recalc();
      return L;
    } else {
      R->l = merge(L, R->l);
      R->recalc();
      return R;
    }
  }
  int cnt(node t) const { return t ? t->cnt : 0; }
  void print(node t) {
    if (t != nullptr) {
      print(t->l);
      if (t->rev) {
        for (int i = 25; i >= 0; i--)
          if (t->c_in_node[i])
            printf("%s", string(t->c_in_node[i], 'a' + i).c_str());
      } else {
        for (int i = 0; i < (26); i++)
          if (t->c_in_node[i])
            printf("%s", string(t->c_in_node[i], 'a' + i).c_str());
      }
      print(t->r);
    }
  }
  void sort(int i, int j, bool rev = false) {
    node L, m, R;
    split(root, j + 1, m, R);
    split(m, i, L, m);
    m->push_sort(rev);
    root = merge(L, merge(m, R));
  }
  void print() {
    print(root);
    putchar('\n');
  }
  void push_back(char c) { root = merge(root, new _node(c)); }
} tree;
const int maxn = 100010;
char buff[maxn];
int main() {
  srand(time(nullptr));
  int n, q;
  scanf("%d%d%s", &n, &q, buff);
  for (int i = 0; i < (n); i++) tree.push_back(buff[i]);
  while (q--) {
    int i, j, k;
    scanf("%d %d %d", &i, &j, &k);
    tree.sort(i - 1, j - 1, 1 - k);
  }
  tree.print();
  return 0;
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

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>
using namespace std;
struct RTC {};
struct Tree {
  typedef struct _node {
    int y, cnt;
    bool sorted_node, rev;
    int c_in_subtree[26], c_in_node[26];
    _node *l, *r;
    _node(char value = 0)
        : y((rand() << 16) ^ rand()), cnt(1), l(nullptr), r(nullptr) {
      memset(c_in_subtree, 0, sizeof(c_in_subtree));
      memset(c_in_node, 0, sizeof(c_in_node));
      sorted_node = rev = false;
      if (value != 0) {
        c_in_subtree[value - 'a'] = 1;
        c_in_node[value - 'a'] = 1;
      }
    }
    ~_node() {
      delete l;
      delete r;
    }
    void recalc() {
      cnt = 0;
      for (int i = 0; i < (26); i++) {
        c_in_subtree[i] = c_in_node[i];
        cnt += c_in_node[i];
      }
      if (l) {
        for (int i = 0; i < (26); i++) c_in_subtree[i] += l->c_in_subtree[i];
        cnt += l->cnt;
      }
      if (r) {
        for (int i = 0; i < (26); i++) c_in_subtree[i] += r->c_in_subtree[i];
        cnt += r->cnt;
      }
    }
    void push_sort(bool re = false) {
      sorted_node = true;
      rev = re;
      cnt = 0;
      for (int i = 0; i < (26); i++) {
        c_in_node[i] = c_in_subtree[i];
        cnt += c_in_subtree[i];
      }
      l = r = nullptr;
    }
  } * node;
  Tree() : root(nullptr) {}
  ~Tree() { delete root; }
  pair<node, node> split_node(node t, int pos) {
    node TL = new _node(), TR = new _node();
    for (int i = 0; i < (26); i++) TR->c_in_node[i] = t->c_in_node[i];
    if (t->rev) {
      TL->rev = true;
      TR->rev = true;
      int take = pos;
      for (int i = 25; i >= 0 && take > 0; i--) {
        if (TR->c_in_node[i] > 0) {
          int tmp = min(take, TR->c_in_node[i]);
          TL->c_in_node[i] = tmp;
          TR->c_in_node[i] -= tmp;
          take -= tmp;
        } else {
          TL->c_in_node[i] = 0;
        }
      }
    } else {
      int take = pos;
      for (int i = 0; i < 26 && take > 0; i++) {
        if (TR->c_in_node[i] > 0) {
          int tmp = min(take, TR->c_in_node[i]);
          TL->c_in_node[i] = tmp;
          TR->c_in_node[i] -= tmp;
          take -= tmp;
        } else {
          TL->c_in_node[i] = 0;
        }
      }
    }
    TL->recalc();
    TR->recalc();
    for (int i = 0; i < (26); i++)
      assert((TL->c_in_node[i]) + (TR->c_in_node[i]) == (t->c_in_node[i]));
    if ((TL->cnt) == 0) TL = nullptr;
    if ((TR->cnt) == 0) TR = nullptr;
    return make_pair(TL, TR);
  }
  node root;
  void split(node t, int x, node &L, node &R) {
    if (t == nullptr) {
      L = R = nullptr;
      return;
    }
    int cnt_in_node = accumulate(t->c_in_node, t->c_in_node + 26, 0);
    int a = cnt(t->l), b = a + cnt_in_node - 1;
    if (cnt_in_node > 1 && a <= x && x <= b) {
      pair<node, node> tmp = split_node(t, x - a);
      L = merge(t->l, tmp.first);
      R = merge(tmp.second, t->r);
    } else {
      int curIndex = cnt(t->l) + cnt_in_node;
      if (curIndex <= x) {
        split(t->r, x - curIndex, t->r, R);
        L = t;
      } else {
        split(t->l, x, L, t->l);
        R = t;
      }
      t->recalc();
    }
  }
  node merge(node L, node R) {
    if (L == nullptr) return R;
    if (R == nullptr) return L;
    if (L->y > R->y) {
      L->r = merge(L->r, R);
      L->recalc();
      return L;
    } else {
      R->l = merge(L, R->l);
      R->recalc();
      return R;
    }
  }
  int cnt(node t) const { return t ? t->cnt : 0; }
  void print(node t) {
    if (t != nullptr) {
      print(t->l);
      if (t->rev) {
        for (int i = 25; i >= 0; i--)
          if (t->c_in_node[i])
            printf("%s", string(t->c_in_node[i], 'a' + i).c_str());
      } else {
        for (int i = 0; i < (26); i++)
          if (t->c_in_node[i])
            printf("%s", string(t->c_in_node[i], 'a' + i).c_str());
      }
      print(t->r);
    }
  }
  void sort(int i, int j, bool rev = false) {
    node L, m, R;
    split(root, j + 1, m, R);
    split(m, i, L, m);
    m->push_sort(rev);
    root = merge(L, merge(m, R));
  }
  void print() {
    print(root);
    putchar('\n');
  }
  void push_back(char c) { root = merge(root, new _node(c)); }
} tree;
const int maxn = 100010;
char buff[maxn];
int main() {
  srand(time(nullptr));
  int n, q;
  scanf("%d%d%s", &n, &q, buff);
  for (int i = 0; i < (n); i++) tree.push_back(buff[i]);
  while (q--) {
    int i, j, k;
    scanf("%d %d %d", &i, &j, &k);
    tree.sort(i - 1, j - 1, 1 - k);
  }
  tree.print();
  return 0;
}

```