#include <bits/stdc++.h>
using namespace std;
const int N = 1 << 17;
struct node {
  int sum, col;
  bool pp;
};
struct STree {
  node t[N + N];
  void push(int v, int tl, int tr) {
    if (!t[v].pp) return;
    t[v].sum = (tr - tl + 1) * t[v].col;
    if (v < N) {
      t[v + v].col = t[v].col;
      t[v + v].pp = 1;
      t[v + v + 1].col = t[v].col;
      t[v + v + 1].pp = 1;
    }
    t[v].pp = 0;
  }
  void color(int l, int r, int x, int v = 1, int tl = 0, int tr = N - 1) {
    push(v, tl, tr);
    if (tl > r || l > tr) return;
    if (tl >= l && tr <= r) {
      t[v].col = x;
      t[v].pp = 1;
      push(v, tl, tr);
      return;
    }
    int tm = (tl + tr) >> 1;
    color(l, r, x, v + v, tl, tm);
    color(l, r, x, v + v + 1, tm + 1, tr);
    t[v].sum = t[v + v].sum + t[v + v + 1].sum;
  }
  int getSum(int l, int r, int v = 1, int tl = 0, int tr = N - 1) {
    push(v, tl, tr);
    if (tl > r || l > tr) return 0;
    if (tl >= l && tr <= r) return t[v].sum;
    int tm = (tl + tr) >> 1;
    return getSum(l, r, v + v, tl, tm) + getSum(l, r, v + v + 1, tm + 1, tr);
  }
  int get(int x) {
    x += N;
    int res = t[x].sum;
    while (x) {
      if (t[x].pp) res = t[x].col;
      x >>= 1;
    }
    return res;
  }
} T[27];
string s;
void debug(int k) {
  for (int i = 0; i < k; i++) {
    cout << char(i + 'a') << ": ";
    for (int j = 0; j < s.length(); j++) cout << T[i].get(j);
    cout << endl;
  }
  cout << endl;
}
int main() {
  int n, q;
  cin >> n >> q;
  cin >> s;
  for (int i = 0; i < s.length(); i++) {
    T[s[i] - 'a'].t[i + N].sum = 1;
  }
  for (int i = 0; i < 26; i++) {
    for (int j = N - 1; j > 0; j--)
      T[i].t[j].sum = T[i].t[j + j].sum + T[i].t[j + j + 1].sum;
  }
  int l, r, k;
  for (int i = 0; i < q; i++) {
    cin >> l >> r >> k;
    l--, r--;
    if (k == 0) {
      int x = l, cnt;
      for (int j = 25; j >= 0; j--) {
        cnt = T[j].getSum(l, r);
        T[j].color(l, r, 0);
        T[j].color(x, x + cnt - 1, 1);
        x += cnt;
      }
    } else {
      int x = l, cnt;
      for (int j = 0; j < 26; j++) {
        cnt = T[j].getSum(l, r);
        T[j].color(l, r, 0);
        T[j].color(x, x + cnt - 1, 1);
        x += cnt;
      }
    }
  }
  for (int i = 0; i < s.length(); i++) {
    for (int j = 0; j < 26; j++)
      if (T[j].get(i) == 1) {
        cout << char(j + 'a');
        break;
      }
  }
  return 0;
}

### 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 = 1 << 17;
struct node {
  int sum, col;
  bool pp;
};
struct STree {
  node t[N + N];
  void push(int v, int tl, int tr) {
    if (!t[v].pp) return;
    t[v].sum = (tr - tl + 1) * t[v].col;
    if (v < N) {
      t[v + v].col = t[v].col;
      t[v + v].pp = 1;
      t[v + v + 1].col = t[v].col;
      t[v + v + 1].pp = 1;
    }
    t[v].pp = 0;
  }
  void color(int l, int r, int x, int v = 1, int tl = 0, int tr = N - 1) {
    push(v, tl, tr);
    if (tl > r || l > tr) return;
    if (tl >= l && tr <= r) {
      t[v].col = x;
      t[v].pp = 1;
      push(v, tl, tr);
      return;
    }
    int tm = (tl + tr) >> 1;
    color(l, r, x, v + v, tl, tm);
    color(l, r, x, v + v + 1, tm + 1, tr);
    t[v].sum = t[v + v].sum + t[v + v + 1].sum;
  }
  int getSum(int l, int r, int v = 1, int tl = 0, int tr = N - 1) {
    push(v, tl, tr);
    if (tl > r || l > tr) return 0;
    if (tl >= l && tr <= r) return t[v].sum;
    int tm = (tl + tr) >> 1;
    return getSum(l, r, v + v, tl, tm) + getSum(l, r, v + v + 1, tm + 1, tr);
  }
  int get(int x) {
    x += N;
    int res = t[x].sum;
    while (x) {
      if (t[x].pp) res = t[x].col;
      x >>= 1;
    }
    return res;
  }
} T[27];
string s;
void debug(int k) {
  for (int i = 0; i < k; i++) {
    cout << char(i + 'a') << ": ";
    for (int j = 0; j < s.length(); j++) cout << T[i].get(j);
    cout << endl;
  }
  cout << endl;
}
int main() {
  int n, q;
  cin >> n >> q;
  cin >> s;
  for (int i = 0; i < s.length(); i++) {
    T[s[i] - 'a'].t[i + N].sum = 1;
  }
  for (int i = 0; i < 26; i++) {
    for (int j = N - 1; j > 0; j--)
      T[i].t[j].sum = T[i].t[j + j].sum + T[i].t[j + j + 1].sum;
  }
  int l, r, k;
  for (int i = 0; i < q; i++) {
    cin >> l >> r >> k;
    l--, r--;
    if (k == 0) {
      int x = l, cnt;
      for (int j = 25; j >= 0; j--) {
        cnt = T[j].getSum(l, r);
        T[j].color(l, r, 0);
        T[j].color(x, x + cnt - 1, 1);
        x += cnt;
      }
    } else {
      int x = l, cnt;
      for (int j = 0; j < 26; j++) {
        cnt = T[j].getSum(l, r);
        T[j].color(l, r, 0);
        T[j].color(x, x + cnt - 1, 1);
        x += cnt;
      }
    }
  }
  for (int i = 0; i < s.length(); i++) {
    for (int j = 0; j < 26; j++)
      if (T[j].get(i) == 1) {
        cout << char(j + 'a');
        break;
      }
  }
  return 0;
}

```