#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1;
const int big = 1e18;
const int block = 800;
const int mod = 1e6;
int n, m;
string a;
struct seg {
  int t[4 * N] = {0};
  bitset<4 * N> u[2];
  void push(int v, int tl, int tr) {
    if (u[0][v]) {
      if (tl != tr)
        u[0][v * 2] = u[0][v * 2 + 1] = u[0][v],
                 u[1][v * 2] = u[1][v * 2 + 1] = u[1][v];
      t[v] = (u[1][v]) * (tr - tl + 1);
      u[0][v] = 0;
    }
  }
  void upd(int l, int r, int z, int v = 1, int tl = 1, int tr = n) {
    push(v, tl, tr);
    if (l > tr || r < tl) return;
    if (l <= tl && tr <= r) {
      u[0][v] = 1;
      u[1][v] = z;
      push(v, tl, tr);
      return;
    }
    int m = (tl + tr) >> 1;
    upd(l, r, z, v * 2, tl, m);
    upd(l, r, z, v * 2 + 1, m + 1, tr);
    t[v] = t[v * 2] + t[v * 2 + 1];
  }
  int get(int l, int r, int v = 1, int tl = 1, int tr = n) {
    push(v, tl, tr);
    if (l > tr || tl > r) return 0;
    if (l <= tl && tr <= r) return t[v];
    int m = (tl + tr) >> 1;
    t[v] = t[v * 2] + t[v * 2 + 1];
    return (get(l, r, v * 2, tl, m) + get(l, r, v * 2 + 1, m + 1, tr));
  }
} rt[26];
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> m >> a;
  for (int i = 0; i < a.size(); i++) {
    rt[a[i] - 'a'].upd(i + 1, i + 1, 1);
  }
  while (m--) {
    int l, r, x;
    cin >> l >> r >> x;
    int st = 0;
    for (int i = 0; i < 26; i++) {
      int y = rt[i].get(l, r);
      if (x == 0) {
        rt[i].upd(l, r, 0);
        rt[i].upd(r - st - y + 1, r - st, 1);
      } else {
        rt[i].upd(l, r, 0);
        rt[i].upd(l + st, l + st + y - 1, 1);
      }
      st += y;
    }
  }
  for (int i = 1; i <= n; i++) {
    char na;
    for (int j = 0; j < 26; j++) {
      if (rt[j].get(i, i)) na = 'a' + j;
    }
    cout << na;
  }
}

### Prompt

Generate 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;
const int N = 1e5 + 1;
const int big = 1e18;
const int block = 800;
const int mod = 1e6;
int n, m;
string a;
struct seg {
  int t[4 * N] = {0};
  bitset<4 * N> u[2];
  void push(int v, int tl, int tr) {
    if (u[0][v]) {
      if (tl != tr)
        u[0][v * 2] = u[0][v * 2 + 1] = u[0][v],
                 u[1][v * 2] = u[1][v * 2 + 1] = u[1][v];
      t[v] = (u[1][v]) * (tr - tl + 1);
      u[0][v] = 0;
    }
  }
  void upd(int l, int r, int z, int v = 1, int tl = 1, int tr = n) {
    push(v, tl, tr);
    if (l > tr || r < tl) return;
    if (l <= tl && tr <= r) {
      u[0][v] = 1;
      u[1][v] = z;
      push(v, tl, tr);
      return;
    }
    int m = (tl + tr) >> 1;
    upd(l, r, z, v * 2, tl, m);
    upd(l, r, z, v * 2 + 1, m + 1, tr);
    t[v] = t[v * 2] + t[v * 2 + 1];
  }
  int get(int l, int r, int v = 1, int tl = 1, int tr = n) {
    push(v, tl, tr);
    if (l > tr || tl > r) return 0;
    if (l <= tl && tr <= r) return t[v];
    int m = (tl + tr) >> 1;
    t[v] = t[v * 2] + t[v * 2 + 1];
    return (get(l, r, v * 2, tl, m) + get(l, r, v * 2 + 1, m + 1, tr));
  }
} rt[26];
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> m >> a;
  for (int i = 0; i < a.size(); i++) {
    rt[a[i] - 'a'].upd(i + 1, i + 1, 1);
  }
  while (m--) {
    int l, r, x;
    cin >> l >> r >> x;
    int st = 0;
    for (int i = 0; i < 26; i++) {
      int y = rt[i].get(l, r);
      if (x == 0) {
        rt[i].upd(l, r, 0);
        rt[i].upd(r - st - y + 1, r - st, 1);
      } else {
        rt[i].upd(l, r, 0);
        rt[i].upd(l + st, l + st + y - 1, 1);
      }
      st += y;
    }
  }
  for (int i = 1; i <= n; i++) {
    char na;
    for (int j = 0; j < 26; j++) {
      if (rt[j].get(i, i)) na = 'a' + j;
    }
    cout << na;
  }
}

```