#include <bits/stdc++.h>
const int MAXINT = 2147483640;
const long long MAXLL = 9223372036854775800LL;
const long long MAXN = 1000000;
using namespace std;
int t[400005][27], g[400005][27];
char s[100005];
void build(int i, int L, int R) {
  if (L == R) {
    t[i][s[L] - 'a'] = 1;
    for (int j = 0; j < 26; j++) g[i][j] = -1;
    return;
  }
  build(i * 2 + 1, L, (L + R) / 2);
  build(i * 2 + 2, (L + R) / 2 + 1, R);
  for (int j = 0; j < 26; j++) {
    g[i][j] = -1;
    t[i][j] = t[i * 2 + 1][j] + t[i * 2 + 2][j];
  }
}
void update(int i, int L, int R, int x, int y, int val, int j) {
  if (g[i][j] != -1) {
    t[i][j] = g[i][j] * (R - L + 1);
    if (L != R) {
      g[i * 2 + 1][j] = g[i][j];
      g[i * 2 + 2][j] = g[i][j];
    }
    g[i][j] = -1;
  }
  if (L >= x && R <= y) {
    g[i][j] = val;
    t[i][j] = g[i][j] * (R - L + 1);
    if (L != R) {
      g[i * 2 + 1][j] = g[i][j];
      g[i * 2 + 2][j] = g[i][j];
    }
    g[i][j] = -1;
    return;
  }
  if (L > y || R < x) return;
  update(i * 2 + 1, L, (L + R) / 2, x, y, val, j);
  update(i * 2 + 2, (L + R) / 2 + 1, R, x, y, val, j);
  t[i][j] = t[i * 2 + 1][j] + t[i * 2 + 2][j];
}
int query(int i, int L, int R, int x, int y, int j) {
  if (g[i][j] != -1) {
    t[i][j] = g[i][j] * (R - L + 1);
    if (L != R) {
      g[i * 2 + 1][j] = g[i][j];
      g[i * 2 + 2][j] = g[i][j];
    }
    g[i][j] = -1;
  }
  if (L >= x && R <= y) return t[i][j];
  if (L > y || R < x) return 0;
  return query(i * 2 + 1, L, (L + R) / 2, x, y, j) +
         query(i * 2 + 2, (L + R) / 2 + 1, R, x, y, j);
}
void get(int i, int L, int R, int j) {
  if (g[i][j] != -1) {
    t[i][j] = g[i][j] * (R - L + 1);
    if (L != R) {
      g[i * 2 + 1][j] = g[i][j];
      g[i * 2 + 2][j] = g[i][j];
    }
    g[i][j] = -1;
  }
  if (!t[i][j]) return;
  if (L == R) {
    s[L] = j + 'a';
    return;
  }
  get(i * 2 + 1, L, (L + R) / 2, j);
  get(i * 2 + 2, (L + R) / 2 + 1, R, j);
}
int cnt[26];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, q, x, y, up;
  cin >> n >> q;
  cin >> s;
  build(0, 0, n - 1);
  for (int i = 0; i < q; i++) {
    cin >> x >> y >> up;
    x--, y--;
    for (int j = 0; j < 26; j++) cnt[j] = query(0, 0, n - 1, x, y, j);
    int curr = x;
    if (!up) curr = y;
    for (int j = 0; j < 26; j++) {
      if (!cnt[j]) continue;
      update(0, 0, n - 1, x, y, 0, j);
      if (up) {
        update(0, 0, n - 1, curr, curr + cnt[j] - 1, 1, j);
        curr += cnt[j];
      } else {
        update(0, 0, n - 1, curr - cnt[j] + 1, curr, 1, j);
        curr -= cnt[j];
      }
    }
  }
  for (int i = 0; i < 26; i++) get(0, 0, n - 1, i);
  cout << s << endl;
  return 0;
}

### Prompt

Create a solution in cpp for 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>
const int MAXINT = 2147483640;
const long long MAXLL = 9223372036854775800LL;
const long long MAXN = 1000000;
using namespace std;
int t[400005][27], g[400005][27];
char s[100005];
void build(int i, int L, int R) {
  if (L == R) {
    t[i][s[L] - 'a'] = 1;
    for (int j = 0; j < 26; j++) g[i][j] = -1;
    return;
  }
  build(i * 2 + 1, L, (L + R) / 2);
  build(i * 2 + 2, (L + R) / 2 + 1, R);
  for (int j = 0; j < 26; j++) {
    g[i][j] = -1;
    t[i][j] = t[i * 2 + 1][j] + t[i * 2 + 2][j];
  }
}
void update(int i, int L, int R, int x, int y, int val, int j) {
  if (g[i][j] != -1) {
    t[i][j] = g[i][j] * (R - L + 1);
    if (L != R) {
      g[i * 2 + 1][j] = g[i][j];
      g[i * 2 + 2][j] = g[i][j];
    }
    g[i][j] = -1;
  }
  if (L >= x && R <= y) {
    g[i][j] = val;
    t[i][j] = g[i][j] * (R - L + 1);
    if (L != R) {
      g[i * 2 + 1][j] = g[i][j];
      g[i * 2 + 2][j] = g[i][j];
    }
    g[i][j] = -1;
    return;
  }
  if (L > y || R < x) return;
  update(i * 2 + 1, L, (L + R) / 2, x, y, val, j);
  update(i * 2 + 2, (L + R) / 2 + 1, R, x, y, val, j);
  t[i][j] = t[i * 2 + 1][j] + t[i * 2 + 2][j];
}
int query(int i, int L, int R, int x, int y, int j) {
  if (g[i][j] != -1) {
    t[i][j] = g[i][j] * (R - L + 1);
    if (L != R) {
      g[i * 2 + 1][j] = g[i][j];
      g[i * 2 + 2][j] = g[i][j];
    }
    g[i][j] = -1;
  }
  if (L >= x && R <= y) return t[i][j];
  if (L > y || R < x) return 0;
  return query(i * 2 + 1, L, (L + R) / 2, x, y, j) +
         query(i * 2 + 2, (L + R) / 2 + 1, R, x, y, j);
}
void get(int i, int L, int R, int j) {
  if (g[i][j] != -1) {
    t[i][j] = g[i][j] * (R - L + 1);
    if (L != R) {
      g[i * 2 + 1][j] = g[i][j];
      g[i * 2 + 2][j] = g[i][j];
    }
    g[i][j] = -1;
  }
  if (!t[i][j]) return;
  if (L == R) {
    s[L] = j + 'a';
    return;
  }
  get(i * 2 + 1, L, (L + R) / 2, j);
  get(i * 2 + 2, (L + R) / 2 + 1, R, j);
}
int cnt[26];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, q, x, y, up;
  cin >> n >> q;
  cin >> s;
  build(0, 0, n - 1);
  for (int i = 0; i < q; i++) {
    cin >> x >> y >> up;
    x--, y--;
    for (int j = 0; j < 26; j++) cnt[j] = query(0, 0, n - 1, x, y, j);
    int curr = x;
    if (!up) curr = y;
    for (int j = 0; j < 26; j++) {
      if (!cnt[j]) continue;
      update(0, 0, n - 1, x, y, 0, j);
      if (up) {
        update(0, 0, n - 1, curr, curr + cnt[j] - 1, 1, j);
        curr += cnt[j];
      } else {
        update(0, 0, n - 1, curr - cnt[j] + 1, curr, 1, j);
        curr -= cnt[j];
      }
    }
  }
  for (int i = 0; i < 26; i++) get(0, 0, n - 1, i);
  cout << s << endl;
  return 0;
}

```