#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 100;
int laz[4 * MAXN][26], seg[4 * MAXN][26];
int chartoint(char c) { return c - 'a'; }
char inttochar(int i) { return 'a' + i; }
void chang(int v, int u, int j, int l, int r) {
  if (laz[v][j] != -1) {
    laz[u][j] = laz[v][j];
    if (laz[u][j]) {
      seg[u][j] = r - l;
    } else {
      seg[u][j] = 0;
    }
  }
}
int ask(int v, int l, int r, int f, int e, int j) {
  if (f <= l && r <= e) {
    return seg[v][j];
  }
  int mid = (l + r) / 2;
  chang(v, 2 * v, j, l, mid);
  chang(v, 2 * v + 1, j, mid, r);
  laz[v][j] = -1;
  int res = 0;
  if (f < mid) {
    res += ask(2 * v, l, mid, f, e, j);
  }
  if (mid < e) {
    res += ask(2 * v + 1, mid, r, f, e, j);
  }
  return res;
}
void sett(int v, int l, int r, int f, int e, bool c, int j) {
  if (r <= l) {
    return;
  }
  if (f <= l && r <= e) {
    laz[v][j] = c;
    if (c) {
      seg[v][j] = r - l;
    } else {
      seg[v][j] = 0;
    }
    return;
  }
  int mid = (l + r) / 2;
  chang(v, 2 * v, j, l, mid);
  chang(v, 2 * v + 1, j, mid, r);
  laz[v][j] = -1;
  if (f < mid) {
    sett(2 * v, l, mid, f, e, c, j);
  }
  if (mid < e) {
    sett(2 * v + 1, mid, r, f, e, c, j);
  }
  seg[v][j] = seg[2 * v][j] + seg[2 * v + 1][j];
  return;
}
int main() {
  int n, q;
  cin >> n >> q;
  string s;
  cin >> s;
  for (int i = 0; i < n; i++) {
    sett(1, 0, n, i, i + 1, 1, chartoint(s[i]));
  }
  int l, r;
  bool c;
  for (int i = 0; i < q; i++) {
    cin >> l >> r >> c;
    l--;
    int a[26];
    for (int j = 0; j < 26; j++) {
      a[j] = ask(1, 0, n, l, r, j);
    }
    if (c) {
      int x = l;
      int j = 0;
      while (x != r) {
        if (a[j]) {
          sett(1, 0, n, l, r, 0, j);
          sett(1, 0, n, x, x + a[j], 1, j);
          x += a[j];
        }
        j++;
      }
    } else {
      int x = l;
      int j = 25;
      while (x != r) {
        if (a[j]) {
          sett(1, 0, n, l, r, 0, j);
          sett(1, 0, n, x, x + a[j], 1, j);
          x += a[j];
        }
        j--;
      }
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 26; j++) {
      if (ask(1, 0, n, i, i + 1, j)) {
        cout << inttochar(j);
        break;
      }
    }
  }
  cout << endl;
}

### Prompt

Please provide a CPP coded solution 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;
const int MAXN = 1e5 + 100;
int laz[4 * MAXN][26], seg[4 * MAXN][26];
int chartoint(char c) { return c - 'a'; }
char inttochar(int i) { return 'a' + i; }
void chang(int v, int u, int j, int l, int r) {
  if (laz[v][j] != -1) {
    laz[u][j] = laz[v][j];
    if (laz[u][j]) {
      seg[u][j] = r - l;
    } else {
      seg[u][j] = 0;
    }
  }
}
int ask(int v, int l, int r, int f, int e, int j) {
  if (f <= l && r <= e) {
    return seg[v][j];
  }
  int mid = (l + r) / 2;
  chang(v, 2 * v, j, l, mid);
  chang(v, 2 * v + 1, j, mid, r);
  laz[v][j] = -1;
  int res = 0;
  if (f < mid) {
    res += ask(2 * v, l, mid, f, e, j);
  }
  if (mid < e) {
    res += ask(2 * v + 1, mid, r, f, e, j);
  }
  return res;
}
void sett(int v, int l, int r, int f, int e, bool c, int j) {
  if (r <= l) {
    return;
  }
  if (f <= l && r <= e) {
    laz[v][j] = c;
    if (c) {
      seg[v][j] = r - l;
    } else {
      seg[v][j] = 0;
    }
    return;
  }
  int mid = (l + r) / 2;
  chang(v, 2 * v, j, l, mid);
  chang(v, 2 * v + 1, j, mid, r);
  laz[v][j] = -1;
  if (f < mid) {
    sett(2 * v, l, mid, f, e, c, j);
  }
  if (mid < e) {
    sett(2 * v + 1, mid, r, f, e, c, j);
  }
  seg[v][j] = seg[2 * v][j] + seg[2 * v + 1][j];
  return;
}
int main() {
  int n, q;
  cin >> n >> q;
  string s;
  cin >> s;
  for (int i = 0; i < n; i++) {
    sett(1, 0, n, i, i + 1, 1, chartoint(s[i]));
  }
  int l, r;
  bool c;
  for (int i = 0; i < q; i++) {
    cin >> l >> r >> c;
    l--;
    int a[26];
    for (int j = 0; j < 26; j++) {
      a[j] = ask(1, 0, n, l, r, j);
    }
    if (c) {
      int x = l;
      int j = 0;
      while (x != r) {
        if (a[j]) {
          sett(1, 0, n, l, r, 0, j);
          sett(1, 0, n, x, x + a[j], 1, j);
          x += a[j];
        }
        j++;
      }
    } else {
      int x = l;
      int j = 25;
      while (x != r) {
        if (a[j]) {
          sett(1, 0, n, l, r, 0, j);
          sett(1, 0, n, x, x + a[j], 1, j);
          x += a[j];
        }
        j--;
      }
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 26; j++) {
      if (ask(1, 0, n, i, i + 1, j)) {
        cout << inttochar(j);
        break;
      }
    }
  }
  cout << endl;
}

```