#include <bits/stdc++.h>
using namespace std;
int const N = 100001;
int n, q, sg[4 * N][27], l, r, lz[4 * N][27];
string g;
void bld(int u, int s, int e, int c) {
  if (s == e) {
    sg[u][c] = (g[s] - 'a' == c);
    return;
  }
  bld(u * 2, s, s + e >> 1, c);
  bld(u * 2 + 1, (s + e >> 1) + 1, e, c);
  sg[u][c] = sg[u * 2][c] + sg[u * 2 + 1][c];
}
void fix(int u, int s, int e, int c) {
  if (lz[u][c] == 2) return;
  sg[u][c] = (e - s + 1) * lz[u][c];
  if (s != e) {
    lz[u * 2][c] = lz[u][c];
    lz[u * 2 + 1][c] = lz[u][c];
  }
  lz[u][c] = 2;
}
void up(int u, int s, int e, int c, int tp) {
  fix(u, s, e, c);
  if (s > r || e < l) return;
  if (s >= l && e <= r) {
    lz[u][c] = tp;
    fix(u, s, e, c);
    return;
  }
  up(u * 2, s, s + e >> 1, c, tp);
  up(u * 2 + 1, (s + e >> 1) + 1, e, c, tp);
  sg[u][c] = sg[u * 2][c] + sg[u * 2 + 1][c];
}
int gt(int u, int s, int e, int c) {
  fix(u, s, e, c);
  if (s > r || e < l) return 0;
  if (s >= l && e <= r) {
    return sg[u][c];
  }
  return gt(u * 2, s, s + e >> 1, c) + gt(u * 2 + 1, (s + e >> 1) + 1, e, c);
}
int main() {
  scanf("%d%d", &n, &q);
  cin >> g;
  for (int i = 0; i < 26; ++i) {
    bld(1, 0, n - 1, i);
  }
  for (int i = 0; i < 4 * n; ++i) {
    for (int j = 0; j < 26; ++j) lz[i][j] = 2;
  }
  for (int qq = 0; qq < q; ++qq) {
    int k, ls, lr;
    scanf("%d%d%d", &ls, &lr, &k);
    --ls, --lr;
    if (k) {
      int take = ls;
      for (int i = 0; i < 26; ++i) {
        l = ls, r = lr;
        int have = gt(1, 0, n - 1, i);
        up(1, 0, n - 1, i, 0);
        l = take;
        r = l + have - 1;
        up(1, 0, n - 1, i, 1);
        have = gt(1, 0, n - 1, i);
        take += have;
      }
      continue;
    } else {
      int take = ls;
      for (int i = 25; i >= 0; --i) {
        l = ls, r = lr;
        int have = gt(1, 0, n - 1, i);
        up(1, 0, n - 1, i, 0);
        l = take;
        r = l + have - 1;
        up(1, 0, n - 1, i, 1);
        have = gt(1, 0, n - 1, i);
        take += have;
      }
    }
  }
  for (int i = 0; i < n; ++i) {
    l = i, r = i;
    for (int j = 0; j < 26; ++j) {
      int yes = gt(1, 0, n - 1, j);
      if (yes) {
        printf("%c", (char)(j + 'a'));
        break;
      }
    }
  }
}

### Prompt

Develop a solution in Cpp 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;
int const N = 100001;
int n, q, sg[4 * N][27], l, r, lz[4 * N][27];
string g;
void bld(int u, int s, int e, int c) {
  if (s == e) {
    sg[u][c] = (g[s] - 'a' == c);
    return;
  }
  bld(u * 2, s, s + e >> 1, c);
  bld(u * 2 + 1, (s + e >> 1) + 1, e, c);
  sg[u][c] = sg[u * 2][c] + sg[u * 2 + 1][c];
}
void fix(int u, int s, int e, int c) {
  if (lz[u][c] == 2) return;
  sg[u][c] = (e - s + 1) * lz[u][c];
  if (s != e) {
    lz[u * 2][c] = lz[u][c];
    lz[u * 2 + 1][c] = lz[u][c];
  }
  lz[u][c] = 2;
}
void up(int u, int s, int e, int c, int tp) {
  fix(u, s, e, c);
  if (s > r || e < l) return;
  if (s >= l && e <= r) {
    lz[u][c] = tp;
    fix(u, s, e, c);
    return;
  }
  up(u * 2, s, s + e >> 1, c, tp);
  up(u * 2 + 1, (s + e >> 1) + 1, e, c, tp);
  sg[u][c] = sg[u * 2][c] + sg[u * 2 + 1][c];
}
int gt(int u, int s, int e, int c) {
  fix(u, s, e, c);
  if (s > r || e < l) return 0;
  if (s >= l && e <= r) {
    return sg[u][c];
  }
  return gt(u * 2, s, s + e >> 1, c) + gt(u * 2 + 1, (s + e >> 1) + 1, e, c);
}
int main() {
  scanf("%d%d", &n, &q);
  cin >> g;
  for (int i = 0; i < 26; ++i) {
    bld(1, 0, n - 1, i);
  }
  for (int i = 0; i < 4 * n; ++i) {
    for (int j = 0; j < 26; ++j) lz[i][j] = 2;
  }
  for (int qq = 0; qq < q; ++qq) {
    int k, ls, lr;
    scanf("%d%d%d", &ls, &lr, &k);
    --ls, --lr;
    if (k) {
      int take = ls;
      for (int i = 0; i < 26; ++i) {
        l = ls, r = lr;
        int have = gt(1, 0, n - 1, i);
        up(1, 0, n - 1, i, 0);
        l = take;
        r = l + have - 1;
        up(1, 0, n - 1, i, 1);
        have = gt(1, 0, n - 1, i);
        take += have;
      }
      continue;
    } else {
      int take = ls;
      for (int i = 25; i >= 0; --i) {
        l = ls, r = lr;
        int have = gt(1, 0, n - 1, i);
        up(1, 0, n - 1, i, 0);
        l = take;
        r = l + have - 1;
        up(1, 0, n - 1, i, 1);
        have = gt(1, 0, n - 1, i);
        take += have;
      }
    }
  }
  for (int i = 0; i < n; ++i) {
    l = i, r = i;
    for (int j = 0; j < 26; ++j) {
      int yes = gt(1, 0, n - 1, j);
      if (yes) {
        printf("%c", (char)(j + 'a'));
        break;
      }
    }
  }
}

```