#include <bits/stdc++.h>
using namespace std;
string s;
vector<vector<int>> tree;
void build(int v, int l, int r) {
  if (r - l == 1) {
    tree[v][s[l] - 'a'] = 1;
    return;
  }
  int m = (l + r) / 2;
  build(v * 2 + 1, l, m);
  build(v * 2 + 2, m, r);
  for (int i = 0; i < 26; i++)
    tree[v][i] = tree[v * 2 + 1][i] + tree[v * 2 + 2][i];
}
vector<int> cnt;
vector<bool> isrev, c;
void push(int v, int l, int r) {
  if (!c[v]) return;
  int m = (l + r) / 2;
  vector<int> parcnt = tree[v];
  if (isrev[v] == false) {
    int left = m - l;
    for (int i = 0; i < 26; i++) {
      tree[v * 2 + 1][i] = 0;
      tree[v * 2 + 1][i] = min(parcnt[i], left);
      parcnt[i] -= tree[v * 2 + 1][i];
      left -= tree[v * 2 + 1][i];
    }
    left = r - m;
    for (int i = 0; i < 26; i++) {
      tree[v * 2 + 2][i] = 0;
      tree[v * 2 + 2][i] = min(parcnt[i], left);
      parcnt[i] -= tree[v * 2 + 2][i];
      left -= tree[v * 2 + 2][i];
    }
    isrev[v * 2 + 1] = isrev[v * 2 + 2] = false;
  } else {
    int left = m - l;
    for (int i = 25; i >= 0; i--) {
      tree[v * 2 + 1][i] = 0;
      tree[v * 2 + 1][i] = min(parcnt[i], left);
      parcnt[i] -= tree[v * 2 + 1][i];
      left -= tree[v * 2 + 1][i];
    }
    left = r - m;
    for (int i = 25; i >= 0; i--) {
      tree[v * 2 + 2][i] = 0;
      tree[v * 2 + 2][i] = min(parcnt[i], left);
      parcnt[i] -= tree[v * 2 + 2][i];
      left -= tree[v * 2 + 2][i];
    }
    isrev[v * 2 + 1] = isrev[v * 2 + 2] = true;
  }
  c[v] = false;
  c[v * 2 + 1] = c[v * 2 + 2] = true;
}
void ask(int v, int l, int r, int askl, int askr) {
  if (r <= askl || askr <= l) return;
  if (askl <= l && r <= askr) {
    for (int i = 0; i < 26; i++) {
      cnt[i] += tree[v][i];
    }
    return;
  }
  push(v, l, r);
  int m = (l + r) / 2;
  ask(v * 2 + 1, l, m, askl, askr);
  ask(v * 2 + 2, m, r, askl, askr);
}
void change(int v, int l, int r, int askl, int askr, int tp) {
  if (r <= askl || askr <= l) return;
  if (askl <= l && r <= askr) {
    int left = (r - l);
    if (tp == 1) {
      isrev[v] = false;
      for (int i = 0; i < 26; i++) {
        tree[v][i] = 0;
        tree[v][i] = min(cnt[i], left);
        cnt[i] -= tree[v][i];
        left -= tree[v][i];
      }
    } else {
      isrev[v] = true;
      for (int i = 25; i >= 0; i--) {
        tree[v][i] = 0;
        tree[v][i] = min(cnt[i], left);
        cnt[i] -= tree[v][i];
        left -= tree[v][i];
      }
    }
    c[v] = true;
    return;
  }
  push(v, l, r);
  int m = (l + r) / 2;
  change(v * 2 + 1, l, m, askl, askr, tp);
  change(v * 2 + 2, m, r, askl, askr, tp);
  for (int i = 0; i < 26; i++)
    tree[v][i] = tree[v * 2 + 1][i] + tree[v * 2 + 2][i];
}
string ans = "";
void answer(int v, int l, int r) {
  if (r - l == 1) {
    for (int i = 0; i < 26; i++)
      if (tree[v][i] == 1) ans.push_back('a' + i);
    return;
  }
  push(v, l, r);
  int m = (l + r) / 2;
  answer(v * 2 + 1, l, m);
  answer(v * 2 + 2, m, r);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n, q;
  cin >> n >> q;
  cin >> s;
  tree.resize(n * 4, vector<int>(26, 0));
  isrev.resize(n * 4, false);
  c.resize(n * 4, false);
  build(0, 0, n);
  for (int i = 0; i < q; i++) {
    int l, r, k;
    cin >> l >> r >> k;
    cnt.assign(26, 0);
    ask(0, 0, n, l - 1, r);
    change(0, 0, n, l - 1, r, k);
  }
  answer(0, 0, n);
  cout << ans;
}

### 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;
string s;
vector<vector<int>> tree;
void build(int v, int l, int r) {
  if (r - l == 1) {
    tree[v][s[l] - 'a'] = 1;
    return;
  }
  int m = (l + r) / 2;
  build(v * 2 + 1, l, m);
  build(v * 2 + 2, m, r);
  for (int i = 0; i < 26; i++)
    tree[v][i] = tree[v * 2 + 1][i] + tree[v * 2 + 2][i];
}
vector<int> cnt;
vector<bool> isrev, c;
void push(int v, int l, int r) {
  if (!c[v]) return;
  int m = (l + r) / 2;
  vector<int> parcnt = tree[v];
  if (isrev[v] == false) {
    int left = m - l;
    for (int i = 0; i < 26; i++) {
      tree[v * 2 + 1][i] = 0;
      tree[v * 2 + 1][i] = min(parcnt[i], left);
      parcnt[i] -= tree[v * 2 + 1][i];
      left -= tree[v * 2 + 1][i];
    }
    left = r - m;
    for (int i = 0; i < 26; i++) {
      tree[v * 2 + 2][i] = 0;
      tree[v * 2 + 2][i] = min(parcnt[i], left);
      parcnt[i] -= tree[v * 2 + 2][i];
      left -= tree[v * 2 + 2][i];
    }
    isrev[v * 2 + 1] = isrev[v * 2 + 2] = false;
  } else {
    int left = m - l;
    for (int i = 25; i >= 0; i--) {
      tree[v * 2 + 1][i] = 0;
      tree[v * 2 + 1][i] = min(parcnt[i], left);
      parcnt[i] -= tree[v * 2 + 1][i];
      left -= tree[v * 2 + 1][i];
    }
    left = r - m;
    for (int i = 25; i >= 0; i--) {
      tree[v * 2 + 2][i] = 0;
      tree[v * 2 + 2][i] = min(parcnt[i], left);
      parcnt[i] -= tree[v * 2 + 2][i];
      left -= tree[v * 2 + 2][i];
    }
    isrev[v * 2 + 1] = isrev[v * 2 + 2] = true;
  }
  c[v] = false;
  c[v * 2 + 1] = c[v * 2 + 2] = true;
}
void ask(int v, int l, int r, int askl, int askr) {
  if (r <= askl || askr <= l) return;
  if (askl <= l && r <= askr) {
    for (int i = 0; i < 26; i++) {
      cnt[i] += tree[v][i];
    }
    return;
  }
  push(v, l, r);
  int m = (l + r) / 2;
  ask(v * 2 + 1, l, m, askl, askr);
  ask(v * 2 + 2, m, r, askl, askr);
}
void change(int v, int l, int r, int askl, int askr, int tp) {
  if (r <= askl || askr <= l) return;
  if (askl <= l && r <= askr) {
    int left = (r - l);
    if (tp == 1) {
      isrev[v] = false;
      for (int i = 0; i < 26; i++) {
        tree[v][i] = 0;
        tree[v][i] = min(cnt[i], left);
        cnt[i] -= tree[v][i];
        left -= tree[v][i];
      }
    } else {
      isrev[v] = true;
      for (int i = 25; i >= 0; i--) {
        tree[v][i] = 0;
        tree[v][i] = min(cnt[i], left);
        cnt[i] -= tree[v][i];
        left -= tree[v][i];
      }
    }
    c[v] = true;
    return;
  }
  push(v, l, r);
  int m = (l + r) / 2;
  change(v * 2 + 1, l, m, askl, askr, tp);
  change(v * 2 + 2, m, r, askl, askr, tp);
  for (int i = 0; i < 26; i++)
    tree[v][i] = tree[v * 2 + 1][i] + tree[v * 2 + 2][i];
}
string ans = "";
void answer(int v, int l, int r) {
  if (r - l == 1) {
    for (int i = 0; i < 26; i++)
      if (tree[v][i] == 1) ans.push_back('a' + i);
    return;
  }
  push(v, l, r);
  int m = (l + r) / 2;
  answer(v * 2 + 1, l, m);
  answer(v * 2 + 2, m, r);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n, q;
  cin >> n >> q;
  cin >> s;
  tree.resize(n * 4, vector<int>(26, 0));
  isrev.resize(n * 4, false);
  c.resize(n * 4, false);
  build(0, 0, n);
  for (int i = 0; i < q; i++) {
    int l, r, k;
    cin >> l >> r >> k;
    cnt.assign(26, 0);
    ask(0, 0, n, l - 1, r);
    change(0, 0, n, l - 1, r, k);
  }
  answer(0, 0, n);
  cout << ans;
}

```