#include <bits/stdc++.h>
using namespace std;
char str[100005];
int Tree[27][400005], Lazy[27][400005], alpha[27], S, E;
void build(int ind, int s, int e) {
  if (s == e) {
    Tree[str[s] - 'a'][ind] = 1;
    return;
  }
  build(ind * 2, s, (s + e) / 2);
  build(ind * 2 + 1, (s + e) / 2 + 1, e);
  for (int j = 0; j < 26; j++)
    Tree[j][ind] = Tree[j][ind * 2] + Tree[j][ind * 2 + 1];
}
int query(int ind, int s, int e, int j) {
  if (Lazy[j][ind] != -1) {
    Tree[j][ind] = Lazy[j][ind] * (e - s + 1);
    if (s != e) {
      Lazy[j][ind * 2] = Lazy[j][ind];
      Lazy[j][ind * 2 + 1] = Lazy[j][ind];
    }
    Lazy[j][ind] = -1;
  }
  if (s > E || e < S) return 0;
  if (s >= S && e <= E) return Tree[j][ind];
  return query(ind * 2, s, (s + e) / 2, j) +
         query(ind * 2 + 1, (s + e) / 2 + 1, e, j);
}
void update(int ind, int s, int e, int val, int j) {
  if (Lazy[j][ind] != -1) {
    Tree[j][ind] = Lazy[j][ind] * (e - s + 1);
    if (s != e) {
      Lazy[j][ind * 2] = Lazy[j][ind];
      Lazy[j][ind * 2 + 1] = Lazy[j][ind];
    }
    Lazy[j][ind] = -1;
  }
  if (s >= S && e <= E) {
    Lazy[j][ind] = val;
    Tree[j][ind] = Lazy[j][ind] * (e - s + 1);
    return;
  }
  if (s > E || e < S) return;
  update(ind * 2, s, (s + e) / 2, val, j);
  update(ind * 2 + 1, (s + e) / 2 + 1, e, val, j);
  Tree[j][ind] = Tree[j][ind * 2] + Tree[j][ind * 2 + 1];
}
void get(int ind, int s, int e, int j) {
  if (Lazy[j][ind] != -1) {
    Tree[j][ind] = Lazy[j][ind] * (e - s + 1);
    if (s != e) {
      Lazy[j][ind * 2] = Lazy[j][ind];
      Lazy[j][ind * 2 + 1] = Lazy[j][ind];
    }
    Lazy[j][ind] = -1;
  }
  if (!Tree[j][ind]) return;
  if (s == e) {
    str[s] = j + 'a';
    return;
  }
  get(ind * 2, s, (s + e) / 2, j);
  get(ind * 2 + 1, (s + e) / 2 + 1, e, j);
}
int main() {
  int n, q, l, r, k;
  scanf("%d%d%s", &n, &q, str);
  memset(Lazy, -1, sizeof Lazy);
  build(1, 0, n - 1);
  for (int i = 0; i < q; i++) {
    scanf("%d%d%d", &l, &r, &k);
    l--;
    r--;
    for (int j = 0; j < 26; j++) {
      S = l;
      E = r;
      alpha[j] = query(1, 0, n - 1, j);
    }
    int cur = l;
    if (!k) {
      for (int j = 25; j >= 0; j--) {
        if (!alpha[j]) continue;
        S = l, E = r;
        update(1, 0, n - 1, 0, j);
        S = cur, E = cur + alpha[j] - 1;
        update(1, 0, n - 1, 1, j);
        cur = E + 1;
      }
    } else {
      for (int j = 0; j < 26; j++) {
        if (!alpha[j]) continue;
        S = l, E = r;
        update(1, 0, n - 1, 0, j);
        S = cur, E = cur + alpha[j] - 1;
        update(1, 0, n - 1, 1, j);
        cur = E + 1;
      }
    }
  }
  for (int j = 0; j < 26; j++) get(1, 0, n - 1, j);
  printf("%s", str);
  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;
char str[100005];
int Tree[27][400005], Lazy[27][400005], alpha[27], S, E;
void build(int ind, int s, int e) {
  if (s == e) {
    Tree[str[s] - 'a'][ind] = 1;
    return;
  }
  build(ind * 2, s, (s + e) / 2);
  build(ind * 2 + 1, (s + e) / 2 + 1, e);
  for (int j = 0; j < 26; j++)
    Tree[j][ind] = Tree[j][ind * 2] + Tree[j][ind * 2 + 1];
}
int query(int ind, int s, int e, int j) {
  if (Lazy[j][ind] != -1) {
    Tree[j][ind] = Lazy[j][ind] * (e - s + 1);
    if (s != e) {
      Lazy[j][ind * 2] = Lazy[j][ind];
      Lazy[j][ind * 2 + 1] = Lazy[j][ind];
    }
    Lazy[j][ind] = -1;
  }
  if (s > E || e < S) return 0;
  if (s >= S && e <= E) return Tree[j][ind];
  return query(ind * 2, s, (s + e) / 2, j) +
         query(ind * 2 + 1, (s + e) / 2 + 1, e, j);
}
void update(int ind, int s, int e, int val, int j) {
  if (Lazy[j][ind] != -1) {
    Tree[j][ind] = Lazy[j][ind] * (e - s + 1);
    if (s != e) {
      Lazy[j][ind * 2] = Lazy[j][ind];
      Lazy[j][ind * 2 + 1] = Lazy[j][ind];
    }
    Lazy[j][ind] = -1;
  }
  if (s >= S && e <= E) {
    Lazy[j][ind] = val;
    Tree[j][ind] = Lazy[j][ind] * (e - s + 1);
    return;
  }
  if (s > E || e < S) return;
  update(ind * 2, s, (s + e) / 2, val, j);
  update(ind * 2 + 1, (s + e) / 2 + 1, e, val, j);
  Tree[j][ind] = Tree[j][ind * 2] + Tree[j][ind * 2 + 1];
}
void get(int ind, int s, int e, int j) {
  if (Lazy[j][ind] != -1) {
    Tree[j][ind] = Lazy[j][ind] * (e - s + 1);
    if (s != e) {
      Lazy[j][ind * 2] = Lazy[j][ind];
      Lazy[j][ind * 2 + 1] = Lazy[j][ind];
    }
    Lazy[j][ind] = -1;
  }
  if (!Tree[j][ind]) return;
  if (s == e) {
    str[s] = j + 'a';
    return;
  }
  get(ind * 2, s, (s + e) / 2, j);
  get(ind * 2 + 1, (s + e) / 2 + 1, e, j);
}
int main() {
  int n, q, l, r, k;
  scanf("%d%d%s", &n, &q, str);
  memset(Lazy, -1, sizeof Lazy);
  build(1, 0, n - 1);
  for (int i = 0; i < q; i++) {
    scanf("%d%d%d", &l, &r, &k);
    l--;
    r--;
    for (int j = 0; j < 26; j++) {
      S = l;
      E = r;
      alpha[j] = query(1, 0, n - 1, j);
    }
    int cur = l;
    if (!k) {
      for (int j = 25; j >= 0; j--) {
        if (!alpha[j]) continue;
        S = l, E = r;
        update(1, 0, n - 1, 0, j);
        S = cur, E = cur + alpha[j] - 1;
        update(1, 0, n - 1, 1, j);
        cur = E + 1;
      }
    } else {
      for (int j = 0; j < 26; j++) {
        if (!alpha[j]) continue;
        S = l, E = r;
        update(1, 0, n - 1, 0, j);
        S = cur, E = cur + alpha[j] - 1;
        update(1, 0, n - 1, 1, j);
        cur = E + 1;
      }
    }
  }
  for (int j = 0; j < 26; j++) get(1, 0, n - 1, j);
  printf("%s", str);
  return 0;
}

```