#include <bits/stdc++.h>
using namespace std;
void SR(int &x) { scanf("%d", &x); }
void SR(long long &x) { scanf("%lld", &x); }
void SR(double &x) { scanf("%lf", &x); }
void SR(char *s) { scanf("%s", s); }
void RI() {}
template <typename I, typename... T>
void RI(I &x, T &...tail) {
  SR(x);
  RI(tail...);
}
struct Treap {
  Treap() {}
  Treap(int k) : pri(rand()), key(k), size(1), lo(0), hi(0), l(0), r(0) {}
  int pri, key, size, lo, hi;
  Treap *l, *r;
};
inline int size(Treap *t) { return t ? t->size : 0; }
inline void push(Treap *t) {
  if (!t->lo) return;
  t->key = t->lo + size(t->l);
  if (t->l) t->l->lo = t->lo, t->l->hi = t->key - 1;
  if (t->r) t->r->hi = t->hi, t->r->lo = t->key + 1;
  t->lo = t->hi = 0;
}
inline void pull(Treap *t) { t->size = size(t->l) + size(t->r) + 1; }
Treap *merge(Treap *a, Treap *b) {
  if (!a || !b)
    return a ? a : b;
  else if (a->pri > b->pri) {
    push(a);
    a->r = merge(a->r, b);
    pull(a);
    return a;
  } else {
    push(b);
    b->l = merge(a, b->l);
    pull(b);
    return b;
  }
}
void split(Treap *t, int k, Treap *&a, Treap *&b) {
  if (!t) {
    a = b = NULL;
    return;
  }
  push(t);
  if (t->key <= k) {
    a = t;
    split(t->r, k, a->r, b);
    pull(a);
  } else {
    b = t;
    split(t->l, k, a, b->l);
    pull(b);
  }
}
const int maxn = 100005;
int n, q;
char s[maxn];
void read() {
  RI(n, q);
  SR(s + 1);
}
Treap *t[128];
void build() {
  for (int i = (1); i <= int(n); i++) t[s[i]] = merge(t[s[i]], new Treap(i));
}
char ans[maxn];
inline void print(Treap *t, char c) {
  if (!t) return;
  push(t);
  ans[t->key] = c;
  print(t->l, c);
  print(t->r, c);
}
void sol() {
  while (q--) {
    int l, r, k;
    RI(l, r, k);
    int rec = l;
    for (char c = (k == 1 ? 'a' : 'z'); islower(c); k == 1 ? c++ : c--) {
      Treap *tl, *tt, *tr;
      split(t[c], r, tt, tr);
      split(tt, l - 1, tl, tt);
      if (tt) {
        tt->lo = rec;
        tt->hi = rec + size(tt) - 1;
      }
      rec += size(tt);
      t[c] = merge(merge(tl, tt), tr);
    }
  }
  for (int i = ('a'); i <= int('z'); i++) print(t[i], i);
  puts(ans + 1);
}
int main() {
  srand(time(NULL));
  read();
  build();
  sol();
  return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

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;
void SR(int &x) { scanf("%d", &x); }
void SR(long long &x) { scanf("%lld", &x); }
void SR(double &x) { scanf("%lf", &x); }
void SR(char *s) { scanf("%s", s); }
void RI() {}
template <typename I, typename... T>
void RI(I &x, T &...tail) {
  SR(x);
  RI(tail...);
}
struct Treap {
  Treap() {}
  Treap(int k) : pri(rand()), key(k), size(1), lo(0), hi(0), l(0), r(0) {}
  int pri, key, size, lo, hi;
  Treap *l, *r;
};
inline int size(Treap *t) { return t ? t->size : 0; }
inline void push(Treap *t) {
  if (!t->lo) return;
  t->key = t->lo + size(t->l);
  if (t->l) t->l->lo = t->lo, t->l->hi = t->key - 1;
  if (t->r) t->r->hi = t->hi, t->r->lo = t->key + 1;
  t->lo = t->hi = 0;
}
inline void pull(Treap *t) { t->size = size(t->l) + size(t->r) + 1; }
Treap *merge(Treap *a, Treap *b) {
  if (!a || !b)
    return a ? a : b;
  else if (a->pri > b->pri) {
    push(a);
    a->r = merge(a->r, b);
    pull(a);
    return a;
  } else {
    push(b);
    b->l = merge(a, b->l);
    pull(b);
    return b;
  }
}
void split(Treap *t, int k, Treap *&a, Treap *&b) {
  if (!t) {
    a = b = NULL;
    return;
  }
  push(t);
  if (t->key <= k) {
    a = t;
    split(t->r, k, a->r, b);
    pull(a);
  } else {
    b = t;
    split(t->l, k, a, b->l);
    pull(b);
  }
}
const int maxn = 100005;
int n, q;
char s[maxn];
void read() {
  RI(n, q);
  SR(s + 1);
}
Treap *t[128];
void build() {
  for (int i = (1); i <= int(n); i++) t[s[i]] = merge(t[s[i]], new Treap(i));
}
char ans[maxn];
inline void print(Treap *t, char c) {
  if (!t) return;
  push(t);
  ans[t->key] = c;
  print(t->l, c);
  print(t->r, c);
}
void sol() {
  while (q--) {
    int l, r, k;
    RI(l, r, k);
    int rec = l;
    for (char c = (k == 1 ? 'a' : 'z'); islower(c); k == 1 ? c++ : c--) {
      Treap *tl, *tt, *tr;
      split(t[c], r, tt, tr);
      split(tt, l - 1, tl, tt);
      if (tt) {
        tt->lo = rec;
        tt->hi = rec + size(tt) - 1;
      }
      rec += size(tt);
      t[c] = merge(merge(tl, tt), tr);
    }
  }
  for (int i = ('a'); i <= int('z'); i++) print(t[i], i);
  puts(ans + 1);
}
int main() {
  srand(time(NULL));
  read();
  build();
  sol();
  return 0;
}

```