#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, q, cnt[100];
char a[N];
struct IT {
  int s[28][4 * N], lazy[28][4 * N];
  void init() {
    memset(s, 0, sizeof(s));
    memset(lazy, -1, sizeof(lazy));
  }
  void pass(int id, int node, int l, int r) {
    if (lazy[id][node] != -1) {
      s[id][node] = lazy[id][node] * (r - l + 1);
      if (l != r) {
        lazy[id][2 * node] = lazy[id][node];
        lazy[id][2 * node + 1] = lazy[id][node];
      }
      lazy[id][node] = -1;
    }
  }
  void build(int id, int node, int l, int r, int p, int q) {
    if (l > q || r < p) return;
    if (l == r) {
      s[id][node] = (a[l] == (char)(id + 'a'));
      return;
    }
    int mid = (l + r) >> 1;
    build(id, 2 * node, l, mid, p, q);
    build(id, 2 * node + 1, mid + 1, r, p, q);
    s[id][node] = s[id][2 * node] + s[id][2 * node + 1];
  }
  void update(int id, int node, int l, int r, int p, int q, int val) {
    pass(id, node, l, r);
    if (l > q || r < p) return;
    if (l >= p && r <= q) {
      lazy[id][node] = val;
      pass(id, node, l, r);
      return;
    }
    int mid = (l + r) >> 1;
    update(id, 2 * node, l, mid, p, q, val);
    update(id, 2 * node + 1, mid + 1, r, p, q, val);
    s[id][node] = s[id][2 * node] + s[id][2 * node + 1];
  }
  int get(int id, int node, int l, int r, int p, int q) {
    pass(id, node, l, r);
    if (l > q || r < p) return 0;
    if (l >= p && r <= q) return s[id][node];
    int mid = (l + r) >> 1;
    return get(id, 2 * node, l, mid, p, q) +
           get(id, 2 * node + 1, mid + 1, r, p, q);
  }
} T;
int main() {
  string s;
  scanf("%d%d", &n, &q);
  cin >> s;
  for (int i = 0; i < s.size(); ++i) a[i + 1] = s[i];
  T.init();
  for (int i = 'a'; i <= 'z'; ++i) T.build(i - 'a', 1, 1, n, 1, n);
  for (int x = 1; x <= q; ++x) {
    int l, r, type;
    scanf("%d%d%d", &l, &r, &type);
    memset(cnt, 0, sizeof(cnt));
    for (int i = 'a'; i <= 'z'; ++i) {
      cnt[i - 'a'] = T.get(i - 'a', 1, 1, n, l, r);
      T.update(i - 'a', 1, 1, n, l, r, 0);
    }
    if (type == 0) {
      int jump = l;
      for (int i = 'z'; i >= 'a'; --i)
        if (cnt[i - 'a']) {
          T.update(i - 'a', 1, 1, n, jump, jump + cnt[i - 'a'] - 1, 1);
          jump += cnt[i - 'a'];
        }
    } else {
      int jump = l;
      for (int i = 'a'; i <= 'z'; ++i) {
        if (cnt[i - 'a']) {
          T.update(i - 'a', 1, 1, n, jump, jump + cnt[i - 'a'] - 1, 1);
          jump += cnt[i - 'a'];
        }
      }
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 'a'; j <= 'z'; ++j)
      if (T.get(j - 'a', 1, 1, n, i, i) == 1) cout << (char)j;
  }
}

### Prompt

Create a solution in cpp for 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 + 5;
int n, q, cnt[100];
char a[N];
struct IT {
  int s[28][4 * N], lazy[28][4 * N];
  void init() {
    memset(s, 0, sizeof(s));
    memset(lazy, -1, sizeof(lazy));
  }
  void pass(int id, int node, int l, int r) {
    if (lazy[id][node] != -1) {
      s[id][node] = lazy[id][node] * (r - l + 1);
      if (l != r) {
        lazy[id][2 * node] = lazy[id][node];
        lazy[id][2 * node + 1] = lazy[id][node];
      }
      lazy[id][node] = -1;
    }
  }
  void build(int id, int node, int l, int r, int p, int q) {
    if (l > q || r < p) return;
    if (l == r) {
      s[id][node] = (a[l] == (char)(id + 'a'));
      return;
    }
    int mid = (l + r) >> 1;
    build(id, 2 * node, l, mid, p, q);
    build(id, 2 * node + 1, mid + 1, r, p, q);
    s[id][node] = s[id][2 * node] + s[id][2 * node + 1];
  }
  void update(int id, int node, int l, int r, int p, int q, int val) {
    pass(id, node, l, r);
    if (l > q || r < p) return;
    if (l >= p && r <= q) {
      lazy[id][node] = val;
      pass(id, node, l, r);
      return;
    }
    int mid = (l + r) >> 1;
    update(id, 2 * node, l, mid, p, q, val);
    update(id, 2 * node + 1, mid + 1, r, p, q, val);
    s[id][node] = s[id][2 * node] + s[id][2 * node + 1];
  }
  int get(int id, int node, int l, int r, int p, int q) {
    pass(id, node, l, r);
    if (l > q || r < p) return 0;
    if (l >= p && r <= q) return s[id][node];
    int mid = (l + r) >> 1;
    return get(id, 2 * node, l, mid, p, q) +
           get(id, 2 * node + 1, mid + 1, r, p, q);
  }
} T;
int main() {
  string s;
  scanf("%d%d", &n, &q);
  cin >> s;
  for (int i = 0; i < s.size(); ++i) a[i + 1] = s[i];
  T.init();
  for (int i = 'a'; i <= 'z'; ++i) T.build(i - 'a', 1, 1, n, 1, n);
  for (int x = 1; x <= q; ++x) {
    int l, r, type;
    scanf("%d%d%d", &l, &r, &type);
    memset(cnt, 0, sizeof(cnt));
    for (int i = 'a'; i <= 'z'; ++i) {
      cnt[i - 'a'] = T.get(i - 'a', 1, 1, n, l, r);
      T.update(i - 'a', 1, 1, n, l, r, 0);
    }
    if (type == 0) {
      int jump = l;
      for (int i = 'z'; i >= 'a'; --i)
        if (cnt[i - 'a']) {
          T.update(i - 'a', 1, 1, n, jump, jump + cnt[i - 'a'] - 1, 1);
          jump += cnt[i - 'a'];
        }
    } else {
      int jump = l;
      for (int i = 'a'; i <= 'z'; ++i) {
        if (cnt[i - 'a']) {
          T.update(i - 'a', 1, 1, n, jump, jump + cnt[i - 'a'] - 1, 1);
          jump += cnt[i - 'a'];
        }
      }
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 'a'; j <= 'z'; ++j)
      if (T.get(j - 'a', 1, 1, n, i, i) == 1) cout << (char)j;
  }
}

```