#include <bits/stdc++.h>
using namespace std;
int n;
class IntervalTreeUp {
 public:
  class Node {
   public:
    int NULL_VALUE = 0;
    Node *l, *r;
    int v, u, c;
    Node() {
      this->u = NULL_VALUE;
      this->v = NULL_VALUE;
      this->l = nullptr;
      this->r = nullptr;
    }
    Node(int v) {
      this->u = NULL_VALUE;
      this->v = v;
      l = new Node();
      r = new Node();
    }
  };
  Node *root;
  IntervalTreeUp() {}
  IntervalTreeUp(int n) {
    _size = n;
    root = new Node();
    _build(root, 1, n);
  }
  ~IntervalTreeUp() {}
  void update(int p, int v) { _update(root, 1, size(), p, v); }
  void update(int l, int r, int v) {
    if (l > r) {
      return;
    }
    _update(root, 1, size(), l, r, v);
  }
  int get(int l, int r) { return _get(root, 1, size(), l, r); }
  int size() { return _size; }

 private:
  int _size;
  int fun(int a, int b) { return a + b; }
  int fun_up(int a, int b) { return b; }
  void perform_up(Node *old, int up) {
    if (old != nullptr) {
      old->u = up;
    }
  }
  int get_mid(int l, int r) { return l + ((r - l + 1) >> 1) - 1; }
  void _build(Node *ver, int l, int r) {
    if (l == r) {
      ver->c = 1;
      return;
    }
    ver->l = new Node();
    ver->r = new Node();
    int m = get_mid(l, r);
    _build(ver->l, l, m);
    _build(ver->r, m + 1, r);
    ver->v = fun(ver->l->v, ver->r->v);
    ver->c = (r - l + 1);
    ver->u = -1;
  }
  void _update(Node *ver, int l, int r, int p, int v) {
    _push(ver);
    if (l == r) {
      ver->v = v;
      return;
    }
    int m = get_mid(l, r);
    if (p > m) {
      _update(ver->r, m + 1, r, p, v);
    } else {
      _update(ver->l, l, m, p, v);
    }
    ver->v = fun(ver->l->v, ver->r->v);
  }
  void _update(Node *ver, int l, int r, int zl, int zr, int up) {
    _push(ver);
    if (zr < l || r < zl) {
      return;
    }
    if (zl <= l && r <= zr) {
      ver->u = fun_up(ver->u, up);
      _push(ver);
      return;
    }
    int m = get_mid(l, r);
    _update(ver->l, l, m, zl, zr, up);
    _update(ver->r, m + 1, r, zl, zr, up);
    ver->v = fun(ver->l->v, ver->r->v);
  }
  int _get(Node *ver, int l, int r, int zl, int zr) {
    _push(ver);
    if (zr < l || r < zl) {
      return 0;
    }
    if (zl <= l && r <= zr) {
      return ver->v;
    }
    int m = get_mid(l, r);
    return fun(_get(ver->l, l, m, zl, zr), _get(ver->r, m + 1, r, zl, zr));
  }
  void _push(Node *ver) {
    if (ver == nullptr) {
      return;
    }
    if (ver->u != -1) {
      perform_up(ver->l, ver->u);
      perform_up(ver->r, ver->u);
      ver->v = ver->c * ver->u;
    }
    ver->u = -1;
  }
};
IntervalTreeUp *str[26];
int cnt[27];
void solve() {
  int q;
  cin >> n >> q;
  string s;
  cin >> s;
  int l, r, k;
  for (int i = 0; i < 26; ++i) {
    str[i] = new IntervalTreeUp(n);
  }
  for (int i = 0; i < n; ++i) {
    str[s[i] - 'a']->update(i + 1, 1);
  }
  for (int i = 0; i < q; ++i) {
    for (int j = 0; j < 27; ++j) {
      cnt[j] = 0;
    }
    scanf("%d%d%d", &l, &r, &k);
    for (int j = 0; j < 26; ++j) {
      cnt[j] = str[j]->get(l, r);
      str[j]->update(l, r, 0);
    }
    int z = 0;
    if (k) {
      for (int j = 25; j >= 0; --j) {
        if (cnt[j] == 0) {
          continue;
        }
        str[j]->update(r - cnt[j] + 1 - z, r - z, 1);
        z += cnt[j];
      }
    } else {
      for (int j = 0; j < 26; ++j) {
        if (cnt[j] == 0) {
          continue;
        }
        str[j]->update(r - cnt[j] + 1 - z, r - z, 1);
        z += cnt[j];
      }
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < 26; ++j) {
      if (str[j]->get(i, i) == 1) {
        printf("%c", (char)('a' + j));
      }
    }
  }
}
int main() {
  solve();
  return 0;
}

### Prompt

Your task is to create 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>
using namespace std;
int n;
class IntervalTreeUp {
 public:
  class Node {
   public:
    int NULL_VALUE = 0;
    Node *l, *r;
    int v, u, c;
    Node() {
      this->u = NULL_VALUE;
      this->v = NULL_VALUE;
      this->l = nullptr;
      this->r = nullptr;
    }
    Node(int v) {
      this->u = NULL_VALUE;
      this->v = v;
      l = new Node();
      r = new Node();
    }
  };
  Node *root;
  IntervalTreeUp() {}
  IntervalTreeUp(int n) {
    _size = n;
    root = new Node();
    _build(root, 1, n);
  }
  ~IntervalTreeUp() {}
  void update(int p, int v) { _update(root, 1, size(), p, v); }
  void update(int l, int r, int v) {
    if (l > r) {
      return;
    }
    _update(root, 1, size(), l, r, v);
  }
  int get(int l, int r) { return _get(root, 1, size(), l, r); }
  int size() { return _size; }

 private:
  int _size;
  int fun(int a, int b) { return a + b; }
  int fun_up(int a, int b) { return b; }
  void perform_up(Node *old, int up) {
    if (old != nullptr) {
      old->u = up;
    }
  }
  int get_mid(int l, int r) { return l + ((r - l + 1) >> 1) - 1; }
  void _build(Node *ver, int l, int r) {
    if (l == r) {
      ver->c = 1;
      return;
    }
    ver->l = new Node();
    ver->r = new Node();
    int m = get_mid(l, r);
    _build(ver->l, l, m);
    _build(ver->r, m + 1, r);
    ver->v = fun(ver->l->v, ver->r->v);
    ver->c = (r - l + 1);
    ver->u = -1;
  }
  void _update(Node *ver, int l, int r, int p, int v) {
    _push(ver);
    if (l == r) {
      ver->v = v;
      return;
    }
    int m = get_mid(l, r);
    if (p > m) {
      _update(ver->r, m + 1, r, p, v);
    } else {
      _update(ver->l, l, m, p, v);
    }
    ver->v = fun(ver->l->v, ver->r->v);
  }
  void _update(Node *ver, int l, int r, int zl, int zr, int up) {
    _push(ver);
    if (zr < l || r < zl) {
      return;
    }
    if (zl <= l && r <= zr) {
      ver->u = fun_up(ver->u, up);
      _push(ver);
      return;
    }
    int m = get_mid(l, r);
    _update(ver->l, l, m, zl, zr, up);
    _update(ver->r, m + 1, r, zl, zr, up);
    ver->v = fun(ver->l->v, ver->r->v);
  }
  int _get(Node *ver, int l, int r, int zl, int zr) {
    _push(ver);
    if (zr < l || r < zl) {
      return 0;
    }
    if (zl <= l && r <= zr) {
      return ver->v;
    }
    int m = get_mid(l, r);
    return fun(_get(ver->l, l, m, zl, zr), _get(ver->r, m + 1, r, zl, zr));
  }
  void _push(Node *ver) {
    if (ver == nullptr) {
      return;
    }
    if (ver->u != -1) {
      perform_up(ver->l, ver->u);
      perform_up(ver->r, ver->u);
      ver->v = ver->c * ver->u;
    }
    ver->u = -1;
  }
};
IntervalTreeUp *str[26];
int cnt[27];
void solve() {
  int q;
  cin >> n >> q;
  string s;
  cin >> s;
  int l, r, k;
  for (int i = 0; i < 26; ++i) {
    str[i] = new IntervalTreeUp(n);
  }
  for (int i = 0; i < n; ++i) {
    str[s[i] - 'a']->update(i + 1, 1);
  }
  for (int i = 0; i < q; ++i) {
    for (int j = 0; j < 27; ++j) {
      cnt[j] = 0;
    }
    scanf("%d%d%d", &l, &r, &k);
    for (int j = 0; j < 26; ++j) {
      cnt[j] = str[j]->get(l, r);
      str[j]->update(l, r, 0);
    }
    int z = 0;
    if (k) {
      for (int j = 25; j >= 0; --j) {
        if (cnt[j] == 0) {
          continue;
        }
        str[j]->update(r - cnt[j] + 1 - z, r - z, 1);
        z += cnt[j];
      }
    } else {
      for (int j = 0; j < 26; ++j) {
        if (cnt[j] == 0) {
          continue;
        }
        str[j]->update(r - cnt[j] + 1 - z, r - z, 1);
        z += cnt[j];
      }
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < 26; ++j) {
      if (str[j]->get(i, i) == 1) {
        printf("%c", (char)('a' + j));
      }
    }
  }
}
int main() {
  solve();
  return 0;
}

```