#include <bits/stdc++.h>
using namespace std;
int n;
int aint[26][3 * 100005], inf[26][3 * 100005];
char sir[100005];
inline void Transmit(int aint[], int inf[], int nod, int st, int dr) {
  if (inf[nod] == -1) return;
  if (!inf[nod])
    aint[2 * nod] = aint[2 * nod + 1] = 0;
  else {
    int mij = ((st + dr) >> 1);
    aint[2 * nod] = mij - st + 1;
    aint[2 * nod + 1] = dr - mij;
  }
  inf[2 * nod] = inf[nod];
  inf[2 * nod + 1] = inf[nod];
  inf[nod] = -1;
}
inline void Upd(int aint[], int inf[], int nod, int st, int dr, int x, int y,
                int tip) {
  if (st == x && dr == y) {
    if (!tip)
      aint[nod] = 0;
    else
      aint[nod] = dr - st + 1;
    inf[nod] = tip;
    return;
  }
  int mij = ((st + dr) >> 1);
  Transmit(aint, inf, nod, st, dr);
  if (y <= mij)
    Upd(aint, inf, 2 * nod, st, mij, x, y, tip);
  else if (x > mij)
    Upd(aint, inf, 2 * nod + 1, mij + 1, dr, x, y, tip);
  else {
    Upd(aint, inf, 2 * nod, st, mij, x, mij, tip);
    Upd(aint, inf, 2 * nod + 1, mij + 1, dr, mij + 1, y, tip);
  }
  aint[nod] = aint[2 * nod] + aint[2 * nod + 1];
}
inline int Query(int aint[], int inf[], int nod, int st, int dr, int x, int y) {
  if (st == x && dr == y) return aint[nod];
  int mij = ((st + dr) >> 1);
  Transmit(aint, inf, nod, st, dr);
  if (y <= mij)
    return Query(aint, inf, 2 * nod, st, mij, x, y);
  else if (x > mij)
    return Query(aint, inf, 2 * nod + 1, mij + 1, dr, x, y);
  else
    return Query(aint, inf, 2 * nod, st, mij, x, mij) +
           Query(aint, inf, 2 * nod + 1, mij + 1, dr, mij + 1, y);
}
int main() {
  int i, j, tip, x, y, m, capat, cnt;
  cin.sync_with_stdio(0);
  cin >> n >> m;
  for (i = 0; i < 26; ++i)
    for (j = 1; j <= 3 * n; ++j) inf[i][j] = -1;
  cin >> (sir + 1);
  for (i = 1; i <= n; ++i)
    Upd(aint[sir[i] - 'a'], inf[sir[i] - 'a'], 1, 1, n, i, i, 1);
  while (m--) {
    cin >> x >> y >> tip;
    capat = x;
    if (tip == 1)
      for (i = 0; i < 26; ++i) {
        cnt = Query(aint[i], inf[i], 1, 1, n, x, y);
        if (!cnt) continue;
        Upd(aint[i], inf[i], 1, 1, n, x, y, 0);
        Upd(aint[i], inf[i], 1, 1, n, capat, capat + cnt - 1, 1);
        capat += cnt;
      }
    else
      for (i = 25; i >= 0; --i) {
        cnt = Query(aint[i], inf[i], 1, 1, n, x, y);
        if (!cnt) continue;
        Upd(aint[i], inf[i], 1, 1, n, x, y, 0);
        Upd(aint[i], inf[i], 1, 1, n, capat, capat + cnt - 1, 1);
        capat += cnt;
      }
  }
  for (i = 1; i <= n; ++i) {
    for (j = 0; j < 26 && !Query(aint[j], inf[j], 1, 1, n, i, i); ++j)
      ;
    cout << char('a' + j);
  }
  return 0;
}

### Prompt

Please formulate 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;
int aint[26][3 * 100005], inf[26][3 * 100005];
char sir[100005];
inline void Transmit(int aint[], int inf[], int nod, int st, int dr) {
  if (inf[nod] == -1) return;
  if (!inf[nod])
    aint[2 * nod] = aint[2 * nod + 1] = 0;
  else {
    int mij = ((st + dr) >> 1);
    aint[2 * nod] = mij - st + 1;
    aint[2 * nod + 1] = dr - mij;
  }
  inf[2 * nod] = inf[nod];
  inf[2 * nod + 1] = inf[nod];
  inf[nod] = -1;
}
inline void Upd(int aint[], int inf[], int nod, int st, int dr, int x, int y,
                int tip) {
  if (st == x && dr == y) {
    if (!tip)
      aint[nod] = 0;
    else
      aint[nod] = dr - st + 1;
    inf[nod] = tip;
    return;
  }
  int mij = ((st + dr) >> 1);
  Transmit(aint, inf, nod, st, dr);
  if (y <= mij)
    Upd(aint, inf, 2 * nod, st, mij, x, y, tip);
  else if (x > mij)
    Upd(aint, inf, 2 * nod + 1, mij + 1, dr, x, y, tip);
  else {
    Upd(aint, inf, 2 * nod, st, mij, x, mij, tip);
    Upd(aint, inf, 2 * nod + 1, mij + 1, dr, mij + 1, y, tip);
  }
  aint[nod] = aint[2 * nod] + aint[2 * nod + 1];
}
inline int Query(int aint[], int inf[], int nod, int st, int dr, int x, int y) {
  if (st == x && dr == y) return aint[nod];
  int mij = ((st + dr) >> 1);
  Transmit(aint, inf, nod, st, dr);
  if (y <= mij)
    return Query(aint, inf, 2 * nod, st, mij, x, y);
  else if (x > mij)
    return Query(aint, inf, 2 * nod + 1, mij + 1, dr, x, y);
  else
    return Query(aint, inf, 2 * nod, st, mij, x, mij) +
           Query(aint, inf, 2 * nod + 1, mij + 1, dr, mij + 1, y);
}
int main() {
  int i, j, tip, x, y, m, capat, cnt;
  cin.sync_with_stdio(0);
  cin >> n >> m;
  for (i = 0; i < 26; ++i)
    for (j = 1; j <= 3 * n; ++j) inf[i][j] = -1;
  cin >> (sir + 1);
  for (i = 1; i <= n; ++i)
    Upd(aint[sir[i] - 'a'], inf[sir[i] - 'a'], 1, 1, n, i, i, 1);
  while (m--) {
    cin >> x >> y >> tip;
    capat = x;
    if (tip == 1)
      for (i = 0; i < 26; ++i) {
        cnt = Query(aint[i], inf[i], 1, 1, n, x, y);
        if (!cnt) continue;
        Upd(aint[i], inf[i], 1, 1, n, x, y, 0);
        Upd(aint[i], inf[i], 1, 1, n, capat, capat + cnt - 1, 1);
        capat += cnt;
      }
    else
      for (i = 25; i >= 0; --i) {
        cnt = Query(aint[i], inf[i], 1, 1, n, x, y);
        if (!cnt) continue;
        Upd(aint[i], inf[i], 1, 1, n, x, y, 0);
        Upd(aint[i], inf[i], 1, 1, n, capat, capat + cnt - 1, 1);
        capat += cnt;
      }
  }
  for (i = 1; i <= n; ++i) {
    for (j = 0; j < 26 && !Query(aint[j], inf[j], 1, 1, n, i, i); ++j)
      ;
    cout << char('a' + j);
  }
  return 0;
}

```