#include <bits/stdc++.h>
using namespace std;
struct S {
  int sorted = -1;
  int frq[26] = {0};
};
S a[1 << 18];
int siz(int i) {
  int tot = 0;
  for (int j = 0; j < (26); j++) tot += a[i].frq[j];
  return tot;
}
S extract(const S& from, int num, int rev) {
  S to;
  int tot = 0;
  for (int j = rev ? 25 : 0; tot < num; j += (rev ? -1 : 1)) {
    int inc = min(num - tot, from.frq[j]);
    to.frq[j] += inc;
    tot += inc;
  }
  return to;
}
S comb(const S& a, const S& b) {
  S r;
  for (int j = 0; j < (26); j++) r.frq[j] = a.frq[j] + b.frq[j];
  return r;
}
void comb(int i) { a[i] = comb(a[2 * i], a[2 * i + 1]); }
void prop(int i) {
  int sorted = a[i].sorted;
  if (sorted == -1) return;
  a[2 * i] = extract(a[i], siz(2 * i), sorted);
  for (int k = 0; k < (26); k++)
    a[2 * i + 1].frq[k] = a[i].frq[k] - a[2 * i].frq[k];
  a[2 * i].sorted = a[2 * i + 1].sorted = sorted;
  a[i].sorted = -1;
}
S query(int i, int j, int c, int l, int r) {
  if (j < l || r < i) return {};
  if (i <= l && r <= j) return a[c];
  prop(c);
  return comb(query(i, j, 2 * c, l, (l + r) / 2),
              query(i, j, 2 * c + 1, (l + r) / 2 + 1, r));
}
void update(int i, int j, S& x, int c, int l, int r) {
  if (j < l || r < i) return;
  if (i <= l && r <= j) {
    a[c] = extract(x, siz(c), x.sorted);
    for (int k = 0; k < (26); k++) x.frq[k] -= a[c].frq[k];
    a[c].sorted = x.sorted;
    return;
  }
  update(i, j, x, 2 * c, l, (l + r) / 2);
  update(i, j, x, 2 * c + 1, (l + r) / 2 + 1, r);
  comb(c);
}
int c = 1;
void sortRange(int i, int j, int k) {
  S cmb = query(i, j, 1, 0, c - 1);
  cmb.sorted = !k;
  update(i, j, cmb, 1, 0, c - 1);
}
void print(int i) {
  switch (a[i].sorted) {
    case -1:
      print(2 * i), print(2 * i + 1);
      break;
    case 0:
      for (int j = 0; j < (26); j++)
        for (int k = 0; k < (a[i].frq[j]); k++) cout << char(j + 'a');
      break;
    case 1:
      for (int j = 26; j--;)
        for (int k = 0; k < (a[i].frq[j]); k++) cout << char(j + 'a');
      break;
  }
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  int n, q;
  cin >> n >> q;
  string s;
  cin >> s;
  while (c < n) c *= 2;
  for (int i = 0; i < (n); i++) a[i + c].frq[s[i] - 'a']++;
  for (int i = 0; i < (c); i++) a[i + c].sorted = 0;
  for (int i = c; i--;)
    if (i) comb(i);
  for (int l = 0; l < (q); l++) {
    int i, j, k;
    cin >> i >> j >> k, i--, j--;
    sortRange(i, j, k);
  }
  print(1), cout << '\n';
}

### Prompt

Your challenge is to write 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;
struct S {
  int sorted = -1;
  int frq[26] = {0};
};
S a[1 << 18];
int siz(int i) {
  int tot = 0;
  for (int j = 0; j < (26); j++) tot += a[i].frq[j];
  return tot;
}
S extract(const S& from, int num, int rev) {
  S to;
  int tot = 0;
  for (int j = rev ? 25 : 0; tot < num; j += (rev ? -1 : 1)) {
    int inc = min(num - tot, from.frq[j]);
    to.frq[j] += inc;
    tot += inc;
  }
  return to;
}
S comb(const S& a, const S& b) {
  S r;
  for (int j = 0; j < (26); j++) r.frq[j] = a.frq[j] + b.frq[j];
  return r;
}
void comb(int i) { a[i] = comb(a[2 * i], a[2 * i + 1]); }
void prop(int i) {
  int sorted = a[i].sorted;
  if (sorted == -1) return;
  a[2 * i] = extract(a[i], siz(2 * i), sorted);
  for (int k = 0; k < (26); k++)
    a[2 * i + 1].frq[k] = a[i].frq[k] - a[2 * i].frq[k];
  a[2 * i].sorted = a[2 * i + 1].sorted = sorted;
  a[i].sorted = -1;
}
S query(int i, int j, int c, int l, int r) {
  if (j < l || r < i) return {};
  if (i <= l && r <= j) return a[c];
  prop(c);
  return comb(query(i, j, 2 * c, l, (l + r) / 2),
              query(i, j, 2 * c + 1, (l + r) / 2 + 1, r));
}
void update(int i, int j, S& x, int c, int l, int r) {
  if (j < l || r < i) return;
  if (i <= l && r <= j) {
    a[c] = extract(x, siz(c), x.sorted);
    for (int k = 0; k < (26); k++) x.frq[k] -= a[c].frq[k];
    a[c].sorted = x.sorted;
    return;
  }
  update(i, j, x, 2 * c, l, (l + r) / 2);
  update(i, j, x, 2 * c + 1, (l + r) / 2 + 1, r);
  comb(c);
}
int c = 1;
void sortRange(int i, int j, int k) {
  S cmb = query(i, j, 1, 0, c - 1);
  cmb.sorted = !k;
  update(i, j, cmb, 1, 0, c - 1);
}
void print(int i) {
  switch (a[i].sorted) {
    case -1:
      print(2 * i), print(2 * i + 1);
      break;
    case 0:
      for (int j = 0; j < (26); j++)
        for (int k = 0; k < (a[i].frq[j]); k++) cout << char(j + 'a');
      break;
    case 1:
      for (int j = 26; j--;)
        for (int k = 0; k < (a[i].frq[j]); k++) cout << char(j + 'a');
      break;
  }
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  int n, q;
  cin >> n >> q;
  string s;
  cin >> s;
  while (c < n) c *= 2;
  for (int i = 0; i < (n); i++) a[i + c].frq[s[i] - 'a']++;
  for (int i = 0; i < (c); i++) a[i + c].sorted = 0;
  for (int i = c; i--;)
    if (i) comb(i);
  for (int l = 0; l < (q); l++) {
    int i, j, k;
    cin >> i >> j >> k, i--, j--;
    sortRange(i, j, k);
  }
  print(1), cout << '\n';
}

```