#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
using namespace std;
const int maxN = (int)1e5 + 1;
int n, q, t[26u][maxN * 4u];
string s;
bool lazy[26u][maxN * 4u];
void build(int v, int tl, int tr, int ind) {
  if (tl == tr)
    t[ind][v] = (int)(s[tl] == char('a' + ind));
  else {
    int tm = tl + tr >> 1u;
    build(v << 1u, tl, tm, ind);
    build(v << 1u | 1u, tm + 1, tr, ind);
    t[ind][v] = t[ind][v << 1u] + t[ind][v << 1u | 1u];
  }
}
void push(int v, int ind, int tl, int tr) {
  if (lazy[ind][v] && tl != tr) {
    lazy[ind][v << 1u] = lazy[ind][v << 1u | 1u] = true;
    int val = t[ind][v] / (tr + 1 - tl), tm = tl + tr >> 1u;
    t[ind][v << 1u] = (tm + 1 - tl) * val;
    t[ind][v << 1u | 1u] = (tr - tm) * val;
    lazy[ind][v] = false;
  }
}
int sum(int v, int tl, int tr, int l, int r, int ind) {
  if (l > r) return 0;
  if (tl == l && tr == r) return t[ind][v];
  int tm = tl + tr >> 1u;
  push(v, ind, tl, tr);
  return sum(v << 1u, tl, tm, l, min(r, tm), ind) +
         sum(v << 1u | 1u, tm + 1, tr, max(l, tm + 1), r, ind);
}
void update(int v, int tl, int tr, int l, int r, int val, int ind) {
  if (l > r) return;
  if (tl == l && tr == r) {
    t[ind][v] = val * (r + 1 - l);
    lazy[ind][v] = true;
    return;
  }
  push(v, ind, tl, tr);
  int tm = tl + tr >> 1u;
  update(v << 1u, tl, tm, l, min(tm, r), val, ind);
  update(v << 1u | 1u, tm + 1, tr, max(l, tm + 1), r, val, ind);
  t[ind][v] = t[ind][v << 1u | 1u] + t[ind][v << 1u];
}
void query(int l, int r, bool reversed) {
  vector<int> cnt(26, 0);
  for (int i = 0; i < 26; i++) {
    cnt[i] = sum(1, 0, n - 1, l, r, i);
    update(1, 0, n - 1, l, r, 0, i);
  }
  if (!reversed) {
    int p = l, L, R;
    for (int i = 0; i < 26; i++) {
      L = p, R = p + cnt[i] - 1;
      update(1, 0, n - 1, L, R, 1, i);
      p += cnt[i];
    }
  } else {
    int p = r, L, R;
    for (int i = 0; i < 26; i++) {
      L = p - cnt[i] + 1, R = p;
      update(1, 0, n - 1, L, R, 1, i);
      p -= cnt[i];
    }
  }
}
int main() {
  cout.tie(nullptr);
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cin >> n >> q >> s;
  for (int i = 0; i < 26; i++) build(1, 0, n - 1, i);
  int l, r, a;
  while (q--) {
    cin >> l >> r >> a;
    query(l - 1, r - 1, a == 0);
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 26; j++) {
      if (sum(1, 0, n - 1, i, i, j)) {
        cout << char('a' + j);
        break;
      }
    }
  }
}

### Prompt

Please create a solution in Cpp 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>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
using namespace std;
const int maxN = (int)1e5 + 1;
int n, q, t[26u][maxN * 4u];
string s;
bool lazy[26u][maxN * 4u];
void build(int v, int tl, int tr, int ind) {
  if (tl == tr)
    t[ind][v] = (int)(s[tl] == char('a' + ind));
  else {
    int tm = tl + tr >> 1u;
    build(v << 1u, tl, tm, ind);
    build(v << 1u | 1u, tm + 1, tr, ind);
    t[ind][v] = t[ind][v << 1u] + t[ind][v << 1u | 1u];
  }
}
void push(int v, int ind, int tl, int tr) {
  if (lazy[ind][v] && tl != tr) {
    lazy[ind][v << 1u] = lazy[ind][v << 1u | 1u] = true;
    int val = t[ind][v] / (tr + 1 - tl), tm = tl + tr >> 1u;
    t[ind][v << 1u] = (tm + 1 - tl) * val;
    t[ind][v << 1u | 1u] = (tr - tm) * val;
    lazy[ind][v] = false;
  }
}
int sum(int v, int tl, int tr, int l, int r, int ind) {
  if (l > r) return 0;
  if (tl == l && tr == r) return t[ind][v];
  int tm = tl + tr >> 1u;
  push(v, ind, tl, tr);
  return sum(v << 1u, tl, tm, l, min(r, tm), ind) +
         sum(v << 1u | 1u, tm + 1, tr, max(l, tm + 1), r, ind);
}
void update(int v, int tl, int tr, int l, int r, int val, int ind) {
  if (l > r) return;
  if (tl == l && tr == r) {
    t[ind][v] = val * (r + 1 - l);
    lazy[ind][v] = true;
    return;
  }
  push(v, ind, tl, tr);
  int tm = tl + tr >> 1u;
  update(v << 1u, tl, tm, l, min(tm, r), val, ind);
  update(v << 1u | 1u, tm + 1, tr, max(l, tm + 1), r, val, ind);
  t[ind][v] = t[ind][v << 1u | 1u] + t[ind][v << 1u];
}
void query(int l, int r, bool reversed) {
  vector<int> cnt(26, 0);
  for (int i = 0; i < 26; i++) {
    cnt[i] = sum(1, 0, n - 1, l, r, i);
    update(1, 0, n - 1, l, r, 0, i);
  }
  if (!reversed) {
    int p = l, L, R;
    for (int i = 0; i < 26; i++) {
      L = p, R = p + cnt[i] - 1;
      update(1, 0, n - 1, L, R, 1, i);
      p += cnt[i];
    }
  } else {
    int p = r, L, R;
    for (int i = 0; i < 26; i++) {
      L = p - cnt[i] + 1, R = p;
      update(1, 0, n - 1, L, R, 1, i);
      p -= cnt[i];
    }
  }
}
int main() {
  cout.tie(nullptr);
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cin >> n >> q >> s;
  for (int i = 0; i < 26; i++) build(1, 0, n - 1, i);
  int l, r, a;
  while (q--) {
    cin >> l >> r >> a;
    query(l - 1, r - 1, a == 0);
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 26; j++) {
      if (sum(1, 0, n - 1, i, i, j)) {
        cout << char('a' + j);
        break;
      }
    }
  }
}

```