#include <bits/stdc++.h>
using namespace std;
struct Node {
  int freq[26]{};
  int lazy = 0;
  Node *left = NULL, *right = NULL;
};
void prop(Node *&it, int l, int r) {
  if (!it->lazy) return;
  if (r - l > 1) {
    if (!it->left) it->left = new Node();
    if (!it->right) it->right = new Node();
    int in1 = (l + r) / 2 - l, in2 = r - (l + r) / 2, got = 0;
    if (it->lazy == 1) {
      for (int i = 0; i < 26; ++i) {
        it->left->freq[i] = 0;
        it->right->freq[i] = 0;
        int x = it->freq[i];
        if (got >= in1)
          it->right->freq[i] += x;
        else {
          int add = min(in1 - got, x);
          it->left->freq[i] += add;
          it->right->freq[i] += x - add;
        }
        got += x;
      }
    } else {
      for (int i = 25; i >= 0; --i) {
        it->left->freq[i] = 0;
        it->right->freq[i] = 0;
        int x = it->freq[i];
        if (got >= in1)
          it->right->freq[i] += x;
        else {
          int add = min(in1 - got, x);
          it->left->freq[i] += add;
          it->right->freq[i] += x - add;
        }
        got += x;
      }
    }
    it->left->lazy = it->lazy;
    it->right->lazy = it->lazy;
  }
  it->lazy = 0;
}
int c[26], ci;
void prepare(Node *&it, int l, int r, int ql, int qr) {
  if (qr <= l || r <= ql) return;
  if (ql <= l && r <= qr) {
    for (int i = 0; i < 26; ++i) c[i] += it->freq[i];
    return;
  }
  if (it->lazy) prop(it, l, r);
  int mid = (l + r) / 2;
  if (!it->left) it->left = new Node();
  if (!it->right) it->right = new Node();
  prepare(it->left, l, mid, ql, qr);
  prepare(it->right, mid, r, ql, qr);
}
void update(Node *&it, int l, int r, int ql, int qr, int type) {
  if (qr <= l || r <= ql) return;
  if (ql <= l && r <= qr) {
    int need = r - l;
    for (int i = 0; i < 26; ++i) it->freq[i] = 0;
    while (ci < 26 && ci > -1 && need > 0) {
      int use = min(need, c[ci]);
      it->freq[ci] += use;
      c[ci] -= use;
      need -= use;
      if (!c[ci]) {
        if (type == 1)
          ++ci;
        else
          --ci;
      }
    }
    it->lazy = type;
    return;
  }
  if (!it->left) it->left = new Node();
  if (!it->right) it->right = new Node();
  int mid = (l + r) / 2;
  update(it->left, l, mid, ql, qr, type);
  update(it->right, mid, r, ql, qr, type);
  for (int i = 0; i < 26; ++i)
    it->freq[i] = it->left->freq[i] + it->right->freq[i];
}
void build(Node *&it, int l, int r, int i, int val) {
  if (r - l == 1) {
    it->freq[val] = 1;
    return;
  }
  if (!it->left) it->left = new Node();
  if (!it->right) it->right = new Node();
  int mid = (l + r) / 2;
  if (i < mid)
    build(it->left, l, mid, i, val);
  else
    build(it->right, mid, r, i, val);
  for (int i = 0; i < 26; ++i)
    it->freq[i] = it->left->freq[i] + it->right->freq[i];
}
string s;
void get(Node *&it, int l, int r) {
  if (r - l == 1) {
    for (int i = 0; i < 26; ++i) {
      if (it->freq[i]) {
        s[l] = 'a' + i;
        break;
      }
    }
  } else {
    if (it->lazy) prop(it, l, r);
    int mid = (l + r) / 2;
    get(it->left, l, mid);
    get(it->right, mid, r);
  }
}
int main() {
  int n, q;
  cin >> n >> q >> s;
  Node *root = new Node();
  for (int i = 0; i < n; ++i) build(root, 0, n, i, s[i] - 'a');
  while (q--) {
    int i, j, k;
    cin >> i >> j >> k;
    --i;
    if (!k) k = 2;
    for (int i = 0; i < 26; ++i) c[i] = 0;
    ci = k == 1 ? 0 : 25;
    prepare(root, 0, n, i, j);
    update(root, 0, n, i, j, k);
  }
  get(root, 0, n);
  cout << s << endl;
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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 Node {
  int freq[26]{};
  int lazy = 0;
  Node *left = NULL, *right = NULL;
};
void prop(Node *&it, int l, int r) {
  if (!it->lazy) return;
  if (r - l > 1) {
    if (!it->left) it->left = new Node();
    if (!it->right) it->right = new Node();
    int in1 = (l + r) / 2 - l, in2 = r - (l + r) / 2, got = 0;
    if (it->lazy == 1) {
      for (int i = 0; i < 26; ++i) {
        it->left->freq[i] = 0;
        it->right->freq[i] = 0;
        int x = it->freq[i];
        if (got >= in1)
          it->right->freq[i] += x;
        else {
          int add = min(in1 - got, x);
          it->left->freq[i] += add;
          it->right->freq[i] += x - add;
        }
        got += x;
      }
    } else {
      for (int i = 25; i >= 0; --i) {
        it->left->freq[i] = 0;
        it->right->freq[i] = 0;
        int x = it->freq[i];
        if (got >= in1)
          it->right->freq[i] += x;
        else {
          int add = min(in1 - got, x);
          it->left->freq[i] += add;
          it->right->freq[i] += x - add;
        }
        got += x;
      }
    }
    it->left->lazy = it->lazy;
    it->right->lazy = it->lazy;
  }
  it->lazy = 0;
}
int c[26], ci;
void prepare(Node *&it, int l, int r, int ql, int qr) {
  if (qr <= l || r <= ql) return;
  if (ql <= l && r <= qr) {
    for (int i = 0; i < 26; ++i) c[i] += it->freq[i];
    return;
  }
  if (it->lazy) prop(it, l, r);
  int mid = (l + r) / 2;
  if (!it->left) it->left = new Node();
  if (!it->right) it->right = new Node();
  prepare(it->left, l, mid, ql, qr);
  prepare(it->right, mid, r, ql, qr);
}
void update(Node *&it, int l, int r, int ql, int qr, int type) {
  if (qr <= l || r <= ql) return;
  if (ql <= l && r <= qr) {
    int need = r - l;
    for (int i = 0; i < 26; ++i) it->freq[i] = 0;
    while (ci < 26 && ci > -1 && need > 0) {
      int use = min(need, c[ci]);
      it->freq[ci] += use;
      c[ci] -= use;
      need -= use;
      if (!c[ci]) {
        if (type == 1)
          ++ci;
        else
          --ci;
      }
    }
    it->lazy = type;
    return;
  }
  if (!it->left) it->left = new Node();
  if (!it->right) it->right = new Node();
  int mid = (l + r) / 2;
  update(it->left, l, mid, ql, qr, type);
  update(it->right, mid, r, ql, qr, type);
  for (int i = 0; i < 26; ++i)
    it->freq[i] = it->left->freq[i] + it->right->freq[i];
}
void build(Node *&it, int l, int r, int i, int val) {
  if (r - l == 1) {
    it->freq[val] = 1;
    return;
  }
  if (!it->left) it->left = new Node();
  if (!it->right) it->right = new Node();
  int mid = (l + r) / 2;
  if (i < mid)
    build(it->left, l, mid, i, val);
  else
    build(it->right, mid, r, i, val);
  for (int i = 0; i < 26; ++i)
    it->freq[i] = it->left->freq[i] + it->right->freq[i];
}
string s;
void get(Node *&it, int l, int r) {
  if (r - l == 1) {
    for (int i = 0; i < 26; ++i) {
      if (it->freq[i]) {
        s[l] = 'a' + i;
        break;
      }
    }
  } else {
    if (it->lazy) prop(it, l, r);
    int mid = (l + r) / 2;
    get(it->left, l, mid);
    get(it->right, mid, r);
  }
}
int main() {
  int n, q;
  cin >> n >> q >> s;
  Node *root = new Node();
  for (int i = 0; i < n; ++i) build(root, 0, n, i, s[i] - 'a');
  while (q--) {
    int i, j, k;
    cin >> i >> j >> k;
    --i;
    if (!k) k = 2;
    for (int i = 0; i < 26; ++i) c[i] = 0;
    ci = k == 1 ? 0 : 25;
    prepare(root, 0, n, i, j);
    update(root, 0, n, i, j, k);
  }
  get(root, 0, n);
  cout << s << endl;
  return 0;
}

```