#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 1000;
string s;
int n, q, seg[4 * maxn][30], lz[4 * maxn][30];
void push(int node, int lnode, int rnode, int x) {
  if (!lz[node][x]) return;
  if (lz[node][x] == 1) {
    int mid = (lnode + rnode) / 2;
    seg[2 * node + 1][x] = mid - lnode;
    seg[2 * node + 2][x] = rnode - mid;
  } else
    seg[2 * node + 1][x] = seg[2 * node + 2][x] = 0;
  lz[2 * node + 1][x] = lz[2 * node + 2][x] = lz[node][x];
  lz[node][x] = 0;
}
void pull(int node, int x) {
  seg[node][x] = seg[2 * node + 1][x] + seg[2 * node + 2][x];
}
int get(int ql, int qr, int x, int node = 0, int lnode = 0, int rnode = n) {
  if (qr <= lnode || rnode <= ql) return 0;
  if (ql <= lnode && rnode <= qr) return seg[node][x];
  int res = 0, mid = (lnode + rnode) / 2;
  push(node, lnode, rnode, x);
  res += get(ql, qr, x, 2 * node + 1, lnode, mid);
  res += get(ql, qr, x, 2 * node + 2, mid, rnode);
  return res;
}
void change(int ql, int qr, int x, int m = 0, int node = 0, int lnode = 0,
            int rnode = n) {
  if (qr <= lnode || rnode <= ql) return;
  if (ql <= lnode && rnode <= qr) {
    seg[node][x] = (rnode - lnode) * m, lz[node][x] = 2 - m;
    return;
  }
  int mid = (lnode + rnode) / 2;
  push(node, lnode, rnode, x);
  change(ql, qr, x, m, 2 * node + 1, lnode, mid);
  change(ql, qr, x, m, 2 * node + 2, mid, rnode);
  pull(node, x);
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cin.tie(0);
  cin >> n >> q;
  cin >> s;
  for (int i = 0; i < n; i++) change(i, i + 1, s[i] - 'a', 1);
  for (; q--;) {
    int l, r, t;
    cin >> l >> r >> t;
    l--;
    if (t) {
      int ind = l;
      for (int i = 0; i < 26; i++) {
        int x = get(l, r, i);
        change(l, r, i);
        change(ind, ind + x, i, 1);
        ind += x;
        if (ind > r) break;
      }
    } else {
      int ind = r;
      for (int i = 0; i < 26; i++) {
        int x = get(l, r, i);
        change(l, r, i);
        change(ind - x, ind, i, 1);
        ind -= x;
        if (ind < l) break;
      }
    }
  }
  for (int i = 0; i < n; i++)
    for (int j = 0; j < 26; j++)
      if (get(i, i + 1, j)) {
        cout << char('a' + j);
        break;
      }
}

### 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 + 1000;
string s;
int n, q, seg[4 * maxn][30], lz[4 * maxn][30];
void push(int node, int lnode, int rnode, int x) {
  if (!lz[node][x]) return;
  if (lz[node][x] == 1) {
    int mid = (lnode + rnode) / 2;
    seg[2 * node + 1][x] = mid - lnode;
    seg[2 * node + 2][x] = rnode - mid;
  } else
    seg[2 * node + 1][x] = seg[2 * node + 2][x] = 0;
  lz[2 * node + 1][x] = lz[2 * node + 2][x] = lz[node][x];
  lz[node][x] = 0;
}
void pull(int node, int x) {
  seg[node][x] = seg[2 * node + 1][x] + seg[2 * node + 2][x];
}
int get(int ql, int qr, int x, int node = 0, int lnode = 0, int rnode = n) {
  if (qr <= lnode || rnode <= ql) return 0;
  if (ql <= lnode && rnode <= qr) return seg[node][x];
  int res = 0, mid = (lnode + rnode) / 2;
  push(node, lnode, rnode, x);
  res += get(ql, qr, x, 2 * node + 1, lnode, mid);
  res += get(ql, qr, x, 2 * node + 2, mid, rnode);
  return res;
}
void change(int ql, int qr, int x, int m = 0, int node = 0, int lnode = 0,
            int rnode = n) {
  if (qr <= lnode || rnode <= ql) return;
  if (ql <= lnode && rnode <= qr) {
    seg[node][x] = (rnode - lnode) * m, lz[node][x] = 2 - m;
    return;
  }
  int mid = (lnode + rnode) / 2;
  push(node, lnode, rnode, x);
  change(ql, qr, x, m, 2 * node + 1, lnode, mid);
  change(ql, qr, x, m, 2 * node + 2, mid, rnode);
  pull(node, x);
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cin.tie(0);
  cin >> n >> q;
  cin >> s;
  for (int i = 0; i < n; i++) change(i, i + 1, s[i] - 'a', 1);
  for (; q--;) {
    int l, r, t;
    cin >> l >> r >> t;
    l--;
    if (t) {
      int ind = l;
      for (int i = 0; i < 26; i++) {
        int x = get(l, r, i);
        change(l, r, i);
        change(ind, ind + x, i, 1);
        ind += x;
        if (ind > r) break;
      }
    } else {
      int ind = r;
      for (int i = 0; i < 26; i++) {
        int x = get(l, r, i);
        change(l, r, i);
        change(ind - x, ind, i, 1);
        ind -= x;
        if (ind < l) break;
      }
    }
  }
  for (int i = 0; i < n; i++)
    for (int j = 0; j < 26; j++)
      if (get(i, i + 1, j)) {
        cout << char('a' + j);
        break;
      }
}

```