#include <bits/stdc++.h>
using namespace std;
const int maxn = 100000 + 5;
const int SIGMA_SIZE = 26;
char s[maxn];
int Sum[SIGMA_SIZE][maxn * 4], tag[SIGMA_SIZE][maxn * 4];
void buildtree(int id, int L, int R) {
  if (L == R) {
    Sum[s[L] - 'a'][id] = 1;
    for (int i = 0; i < 26; i++) tag[i][id] = -1;
    return;
  }
  int M = (L + R) >> 1;
  buildtree(id << 1, L, M);
  buildtree(id << 1 | 1, M + 1, R);
  for (int i = 0; i < 26; i++)
    Sum[i][id] = Sum[i][id << 1] + Sum[i][id << 1 | 1], tag[i][id] = -1;
}
inline void push(int id, int i) {
  if (tag[i][id] != -1) {
    tag[i][id << 1] = tag[i][id << 1 | 1] = tag[i][id];
    tag[i][id] = -1;
  }
}
inline void pull(int id, int i, int L, int R) {
  int M = (L + R) >> 1;
  Sum[i][id] = (tag[i][id << 1] == -1 ? Sum[i][id << 1]
                                      : tag[i][id << 1] * (M - L + 1)) +
               (tag[i][id << 1 | 1] == -1 ? Sum[i][id << 1 | 1]
                                          : tag[i][id << 1 | 1] * (R - M));
}
void qsum(int id, int L, int R, int qL, int qR, int* cnt) {
  if (qL <= L && R <= qR) {
    for (int i = 0; i < 26; i++)
      cnt[i] += (tag[i][id] == -1 ? Sum[i][id] : tag[i][id] * (R - L + 1));
    return;
  }
  for (int i = 0; i < 26; i++) push(id, i);
  int M = (L + R) >> 1;
  if (qL <= M) qsum(id << 1, L, M, qL, qR, cnt);
  if (qR > M) qsum(id << 1 | 1, M + 1, R, qL, qR, cnt);
  for (int i = 0; i < 26; i++) pull(id, i, L, R);
}
void modify(int id, int L, int R, int mL, int mR, int mtype, int mv) {
  if (mL <= L && R <= mR) {
    tag[mtype][id] = mv;
    return;
  }
  push(id, mtype);
  int M = (L + R) >> 1;
  if (mL <= M) modify(id << 1, L, M, mL, mR, mtype, mv);
  if (mR > M) modify(id << 1 | 1, M + 1, R, mL, mR, mtype, mv);
  pull(id, mtype, L, R);
}
void buildans(int id, int L, int R) {
  if (L == R) {
    for (int i = 0; i < 26; i++)
      if (tag[i][id] == 1 || (tag[i][id] != 0 && Sum[i][id] == 1)) {
        printf("%c", i + 'a');
        return;
      }
    assert(0);
  }
  for (int i = 0; i < 26; i++) push(id, i);
  int M = (L + R) >> 1;
  buildans(id << 1, L, M);
  buildans(id << 1 | 1, M + 1, R);
  for (int i = 0; i < 26; i++) pull(id, i, L, R);
}
int main() {
  int n, q;
  scanf("%d%d%s", &n, &q, s);
  buildtree(1, 0, n - 1);
  while (q--) {
    int L, R, inc;
    scanf("%d%d%d", &L, &R, &inc);
    L--, R--;
    int cnt[26] = {0};
    qsum(1, 0, n - 1, L, R, cnt);
    int st = inc ? 0 : 25, ed = inc ? 26 : -1, add = inc ? 1 : -1, p = L;
    for (int i = st; i != ed; i += add)
      if (cnt[i]) {
        modify(1, 0, n - 1, L, R, i, 0);
        modify(1, 0, n - 1, p, p + cnt[i] - 1, i, 1);
        p += cnt[i];
      }
  }
  buildans(1, 0, n - 1);
  puts("");
}

### 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>
using namespace std;
const int maxn = 100000 + 5;
const int SIGMA_SIZE = 26;
char s[maxn];
int Sum[SIGMA_SIZE][maxn * 4], tag[SIGMA_SIZE][maxn * 4];
void buildtree(int id, int L, int R) {
  if (L == R) {
    Sum[s[L] - 'a'][id] = 1;
    for (int i = 0; i < 26; i++) tag[i][id] = -1;
    return;
  }
  int M = (L + R) >> 1;
  buildtree(id << 1, L, M);
  buildtree(id << 1 | 1, M + 1, R);
  for (int i = 0; i < 26; i++)
    Sum[i][id] = Sum[i][id << 1] + Sum[i][id << 1 | 1], tag[i][id] = -1;
}
inline void push(int id, int i) {
  if (tag[i][id] != -1) {
    tag[i][id << 1] = tag[i][id << 1 | 1] = tag[i][id];
    tag[i][id] = -1;
  }
}
inline void pull(int id, int i, int L, int R) {
  int M = (L + R) >> 1;
  Sum[i][id] = (tag[i][id << 1] == -1 ? Sum[i][id << 1]
                                      : tag[i][id << 1] * (M - L + 1)) +
               (tag[i][id << 1 | 1] == -1 ? Sum[i][id << 1 | 1]
                                          : tag[i][id << 1 | 1] * (R - M));
}
void qsum(int id, int L, int R, int qL, int qR, int* cnt) {
  if (qL <= L && R <= qR) {
    for (int i = 0; i < 26; i++)
      cnt[i] += (tag[i][id] == -1 ? Sum[i][id] : tag[i][id] * (R - L + 1));
    return;
  }
  for (int i = 0; i < 26; i++) push(id, i);
  int M = (L + R) >> 1;
  if (qL <= M) qsum(id << 1, L, M, qL, qR, cnt);
  if (qR > M) qsum(id << 1 | 1, M + 1, R, qL, qR, cnt);
  for (int i = 0; i < 26; i++) pull(id, i, L, R);
}
void modify(int id, int L, int R, int mL, int mR, int mtype, int mv) {
  if (mL <= L && R <= mR) {
    tag[mtype][id] = mv;
    return;
  }
  push(id, mtype);
  int M = (L + R) >> 1;
  if (mL <= M) modify(id << 1, L, M, mL, mR, mtype, mv);
  if (mR > M) modify(id << 1 | 1, M + 1, R, mL, mR, mtype, mv);
  pull(id, mtype, L, R);
}
void buildans(int id, int L, int R) {
  if (L == R) {
    for (int i = 0; i < 26; i++)
      if (tag[i][id] == 1 || (tag[i][id] != 0 && Sum[i][id] == 1)) {
        printf("%c", i + 'a');
        return;
      }
    assert(0);
  }
  for (int i = 0; i < 26; i++) push(id, i);
  int M = (L + R) >> 1;
  buildans(id << 1, L, M);
  buildans(id << 1 | 1, M + 1, R);
  for (int i = 0; i < 26; i++) pull(id, i, L, R);
}
int main() {
  int n, q;
  scanf("%d%d%s", &n, &q, s);
  buildtree(1, 0, n - 1);
  while (q--) {
    int L, R, inc;
    scanf("%d%d%d", &L, &R, &inc);
    L--, R--;
    int cnt[26] = {0};
    qsum(1, 0, n - 1, L, R, cnt);
    int st = inc ? 0 : 25, ed = inc ? 26 : -1, add = inc ? 1 : -1, p = L;
    for (int i = st; i != ed; i += add)
      if (cnt[i]) {
        modify(1, 0, n - 1, L, R, i, 0);
        modify(1, 0, n - 1, p, p + cnt[i] - 1, i, 1);
        p += cnt[i];
      }
  }
  buildans(1, 0, n - 1);
  puts("");
}

```