#include <bits/stdc++.h>
using namespace std;
int n, Q, i, j, a, b, c, l;
int t[400005][27], d[400005];
int A[27];
string S, answ;
void push(int v, int s, int e) {
  if (s == e || d[v] == -1) return;
  if (d[v] == -2) {
    for (int i = 0; i < 26; i++) t[2 * v][i] = t[2 * v + 1][i] = 0;
    d[2 * v] = d[2 * v + 1] = -2;
    d[v] = -1;
    return;
  }
  d[2 * v] = d[2 * v + 1] = d[v];
  int m = (s + e) / 2;
  for (int i = 0; i < 26; i++) {
    if (i == d[2 * v]) {
      t[2 * v][i] = m - s + 1;
      t[2 * v + 1][i] = e - m;
    } else {
      t[2 * v][i] = 0;
      t[2 * v + 1][i] = 0;
    }
  }
  d[v] = -1;
}
void build(int v, int s, int e) {
  d[v] = -1;
  if (s == e) {
    for (int i = 0; i < 26; i++) {
      char k = char('a' + i);
      if (k == S[s]) t[v][i]++;
    }
    return;
  }
  int m = (s + e) / 2;
  build(2 * v, s, m);
  build(2 * v + 1, m + 1, e);
  for (int i = 0; i < 26; i++) t[v][i] = t[2 * v][i] + t[2 * v + 1][i];
}
int query(int v, int s, int e, int l, int r, int delta) {
  if (l > r) return 0;
  push(v, s, e);
  if (l == s && e == r) {
    int k = t[v][delta];
    return k;
  }
  int m = (s + e) / 2;
  return query(2 * v, s, m, l, min(r, m), delta) +
         query(2 * v + 1, m + 1, e, max(m + 1, l), r, delta);
}
void update0(int v, int s, int e, int l, int r) {
  if (l > r) return;
  push(v, s, e);
  if (l == s && e == r) {
    for (int i = 0; i < 26; i++) t[v][i] = 0;
    d[v] = -2;
    return;
  }
  int m = (s + e) / 2;
  update0(2 * v, s, m, l, min(r, m));
  update0(2 * v + 1, m + 1, e, max(m + 1, l), r);
  for (int i = 0; i < 26; i++) t[v][i] = t[2 * v][i] + t[2 * v + 1][i];
}
void update(int v, int s, int e, int l, int r, int delta) {
  if (l > r) return;
  push(v, s, e);
  if (l == s && e == r) {
    t[v][delta] = r - l + 1;
    d[v] = delta;
    return;
  }
  int m = (s + e) / 2;
  update(2 * v, s, m, l, min(r, m), delta);
  update(2 * v + 1, m + 1, e, max(m + 1, l), r, delta);
  t[v][delta] = t[2 * v][delta] + t[2 * v + 1][delta];
}
int Query(int v, int s, int e, int pos) {
  push(v, s, e);
  if (s == e) {
    for (int i = 0; i < 26; i++) {
      if (t[v][i] == 0) continue;
      return i;
    }
  }
  int m = (s + e) / 2;
  if (pos <= m) return Query(2 * v, s, m, pos);
  return Query(2 * v + 1, m + 1, e, pos);
}
int main() {
  scanf("%d%d", &n, &Q);
  cin >> S;
  build(1, 0, n - 1);
  for (i = 1; i <= Q; i++) {
    scanf("%d%d%d", &a, &b, &c);
    a--;
    b--;
    for (j = 0; j <= 26; j++) A[j] = query(1, 0, n - 1, a, b, j);
    update0(1, 0, n - 1, a, b);
    l = 0;
    if (c == 0) {
      for (j = 25; j >= 0; j--) {
        update(1, 0, n - 1, a + l, a + l + A[j] - 1, j);
        l += A[j];
      }
    } else {
      for (j = 0; j < 26; j++) {
        update(1, 0, n - 1, a + l, a + l + A[j] - 1, j);
        l += A[j];
      }
    }
  }
  for (i = 0; i < n; i++) {
    int k = Query(1, 0, n - 1, i);
    answ += char('a' + k);
  }
  cout << answ << endl;
  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, Q, i, j, a, b, c, l;
int t[400005][27], d[400005];
int A[27];
string S, answ;
void push(int v, int s, int e) {
  if (s == e || d[v] == -1) return;
  if (d[v] == -2) {
    for (int i = 0; i < 26; i++) t[2 * v][i] = t[2 * v + 1][i] = 0;
    d[2 * v] = d[2 * v + 1] = -2;
    d[v] = -1;
    return;
  }
  d[2 * v] = d[2 * v + 1] = d[v];
  int m = (s + e) / 2;
  for (int i = 0; i < 26; i++) {
    if (i == d[2 * v]) {
      t[2 * v][i] = m - s + 1;
      t[2 * v + 1][i] = e - m;
    } else {
      t[2 * v][i] = 0;
      t[2 * v + 1][i] = 0;
    }
  }
  d[v] = -1;
}
void build(int v, int s, int e) {
  d[v] = -1;
  if (s == e) {
    for (int i = 0; i < 26; i++) {
      char k = char('a' + i);
      if (k == S[s]) t[v][i]++;
    }
    return;
  }
  int m = (s + e) / 2;
  build(2 * v, s, m);
  build(2 * v + 1, m + 1, e);
  for (int i = 0; i < 26; i++) t[v][i] = t[2 * v][i] + t[2 * v + 1][i];
}
int query(int v, int s, int e, int l, int r, int delta) {
  if (l > r) return 0;
  push(v, s, e);
  if (l == s && e == r) {
    int k = t[v][delta];
    return k;
  }
  int m = (s + e) / 2;
  return query(2 * v, s, m, l, min(r, m), delta) +
         query(2 * v + 1, m + 1, e, max(m + 1, l), r, delta);
}
void update0(int v, int s, int e, int l, int r) {
  if (l > r) return;
  push(v, s, e);
  if (l == s && e == r) {
    for (int i = 0; i < 26; i++) t[v][i] = 0;
    d[v] = -2;
    return;
  }
  int m = (s + e) / 2;
  update0(2 * v, s, m, l, min(r, m));
  update0(2 * v + 1, m + 1, e, max(m + 1, l), r);
  for (int i = 0; i < 26; i++) t[v][i] = t[2 * v][i] + t[2 * v + 1][i];
}
void update(int v, int s, int e, int l, int r, int delta) {
  if (l > r) return;
  push(v, s, e);
  if (l == s && e == r) {
    t[v][delta] = r - l + 1;
    d[v] = delta;
    return;
  }
  int m = (s + e) / 2;
  update(2 * v, s, m, l, min(r, m), delta);
  update(2 * v + 1, m + 1, e, max(m + 1, l), r, delta);
  t[v][delta] = t[2 * v][delta] + t[2 * v + 1][delta];
}
int Query(int v, int s, int e, int pos) {
  push(v, s, e);
  if (s == e) {
    for (int i = 0; i < 26; i++) {
      if (t[v][i] == 0) continue;
      return i;
    }
  }
  int m = (s + e) / 2;
  if (pos <= m) return Query(2 * v, s, m, pos);
  return Query(2 * v + 1, m + 1, e, pos);
}
int main() {
  scanf("%d%d", &n, &Q);
  cin >> S;
  build(1, 0, n - 1);
  for (i = 1; i <= Q; i++) {
    scanf("%d%d%d", &a, &b, &c);
    a--;
    b--;
    for (j = 0; j <= 26; j++) A[j] = query(1, 0, n - 1, a, b, j);
    update0(1, 0, n - 1, a, b);
    l = 0;
    if (c == 0) {
      for (j = 25; j >= 0; j--) {
        update(1, 0, n - 1, a + l, a + l + A[j] - 1, j);
        l += A[j];
      }
    } else {
      for (j = 0; j < 26; j++) {
        update(1, 0, n - 1, a + l, a + l + A[j] - 1, j);
        l += A[j];
      }
    }
  }
  for (i = 0; i < n; i++) {
    int k = Query(1, 0, n - 1, i);
    answ += char('a' + k);
  }
  cout << answ << endl;
  return 0;
}

```