#include <bits/stdc++.h>
#pragma GCC optimize(2, "Ofast", "inline", "-fgcse", "-fgcse-lm", "-fipa-sra", \
                     "-ftree-pre", "-ftree-vrp", "-fpeephole2", "-ffast-math", \
                     "-fsched-spec", "unroll-loops", "-falign-jumps",          \
                     "-falign-loops", "-falign-labels", "-fdevirtualize",      \
                     "-fcaller-saves", "-fcrossjumping", "-fthread-jumps",     \
                     "-funroll-loops")
#pragma GCC target( \
    "sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
using namespace std::chrono;
char BB[1 << 15], *SS = BB, *TT = BB;
inline int read() {
  int s = 0;
  char ch =
      (SS == TT && (TT = (SS = BB) + fread(BB, 1, 1 << 15, stdin), SS == TT)
           ? EOF
           : *SS++);
  while (!((ch >= '0') && (ch <= '9')))
    ch = (SS == TT && (TT = (SS = BB) + fread(BB, 1, 1 << 15, stdin), SS == TT)
              ? EOF
              : *SS++);
  while (((ch >= '0') && (ch <= '9')))
    s = (s << 3) + (s << 1) + (ch ^ 48),
    ch = (SS == TT && (TT = (SS = BB) + fread(BB, 1, 1 << 15, stdin), SS == TT)
              ? EOF
              : *SS++);
  return s;
}
inline char rad() {
  char ch =
      (SS == TT && (TT = (SS = BB) + fread(BB, 1, 1 << 15, stdin), SS == TT)
           ? EOF
           : *SS++);
  while (!((ch >= 'a') && (ch <= 'z')))
    ch = (SS == TT && (TT = (SS = BB) + fread(BB, 1, 1 << 15, stdin), SS == TT)
              ? EOF
              : *SS++);
  return ch ^ 96;
}
using namespace std;
struct node {
  int l, r, v;
  node(int L, int R = -1, int V = 0) : l(L), r(R), v(V) {}
  bool operator<(const node &o) const { return l < o.l; }
};
set<node> s;
set<node>::iterator split(int pos) {
  set<node>::iterator it = s.lower_bound(node(pos));
  if (it != s.end() && it->l == pos) return it;
  --it;
  int L = it->l, R = it->r;
  int V = it->v;
  s.erase(it);
  s.insert(node(L, pos - 1, V));
  return s.insert(node(pos, R, V)).first;
}
int ton[30];
int n, q, ll, a, b;
int main() {
  n = read(), q = read();
  ll = 1, b = a = rad();
  for (register int i = 2; i <= n; ++i) {
    a = rad();
    if (a ^ b) {
      s.insert(node(ll, i - 1, b));
      ll = i;
    }
    b = a;
  }
  s.insert(node(ll, n, a));
  s.insert(node(n + 1, n + 1, 30));
  register int tmc, el, er;
  for (register int i = 1; i <= q; ++i) {
    el = read(), er = read(), tmc = read();
    for (int j = 1; j <= 26; ++j) {
      ton[j] = 0;
    }
    set<node>::iterator itr = split(er + 1), itl = split(el);
    for (set<node>::iterator tm = itl; tm != itr; ++tm) {
      ton[tm->v] += tm->r - tm->l + 1;
    }
    s.erase(itl, itr);
    if (tmc) {
      for (int j = 1; j <= 26; ++j) {
        if (ton[j]) {
          s.insert(node(el, el + ton[j] - 1, j));
          el = el + ton[j];
        }
      }
    } else {
      for (int j = 26; j >= 1; --j) {
        if (ton[j]) {
          s.insert(node(el, el + ton[j] - 1, j));
          el = el + ton[j];
        }
      }
    }
  }
  set<node>::iterator k = s.begin();
  ++k;
  for (set<node>::iterator i = s.begin(); k != s.end(); ++i, ++k)
    for (int j = i->l; j <= i->r; ++j) putchar(i->v ^ 96);
  printf("\n");
  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>
#pragma GCC optimize(2, "Ofast", "inline", "-fgcse", "-fgcse-lm", "-fipa-sra", \
                     "-ftree-pre", "-ftree-vrp", "-fpeephole2", "-ffast-math", \
                     "-fsched-spec", "unroll-loops", "-falign-jumps",          \
                     "-falign-loops", "-falign-labels", "-fdevirtualize",      \
                     "-fcaller-saves", "-fcrossjumping", "-fthread-jumps",     \
                     "-funroll-loops")
#pragma GCC target( \
    "sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
using namespace std::chrono;
char BB[1 << 15], *SS = BB, *TT = BB;
inline int read() {
  int s = 0;
  char ch =
      (SS == TT && (TT = (SS = BB) + fread(BB, 1, 1 << 15, stdin), SS == TT)
           ? EOF
           : *SS++);
  while (!((ch >= '0') && (ch <= '9')))
    ch = (SS == TT && (TT = (SS = BB) + fread(BB, 1, 1 << 15, stdin), SS == TT)
              ? EOF
              : *SS++);
  while (((ch >= '0') && (ch <= '9')))
    s = (s << 3) + (s << 1) + (ch ^ 48),
    ch = (SS == TT && (TT = (SS = BB) + fread(BB, 1, 1 << 15, stdin), SS == TT)
              ? EOF
              : *SS++);
  return s;
}
inline char rad() {
  char ch =
      (SS == TT && (TT = (SS = BB) + fread(BB, 1, 1 << 15, stdin), SS == TT)
           ? EOF
           : *SS++);
  while (!((ch >= 'a') && (ch <= 'z')))
    ch = (SS == TT && (TT = (SS = BB) + fread(BB, 1, 1 << 15, stdin), SS == TT)
              ? EOF
              : *SS++);
  return ch ^ 96;
}
using namespace std;
struct node {
  int l, r, v;
  node(int L, int R = -1, int V = 0) : l(L), r(R), v(V) {}
  bool operator<(const node &o) const { return l < o.l; }
};
set<node> s;
set<node>::iterator split(int pos) {
  set<node>::iterator it = s.lower_bound(node(pos));
  if (it != s.end() && it->l == pos) return it;
  --it;
  int L = it->l, R = it->r;
  int V = it->v;
  s.erase(it);
  s.insert(node(L, pos - 1, V));
  return s.insert(node(pos, R, V)).first;
}
int ton[30];
int n, q, ll, a, b;
int main() {
  n = read(), q = read();
  ll = 1, b = a = rad();
  for (register int i = 2; i <= n; ++i) {
    a = rad();
    if (a ^ b) {
      s.insert(node(ll, i - 1, b));
      ll = i;
    }
    b = a;
  }
  s.insert(node(ll, n, a));
  s.insert(node(n + 1, n + 1, 30));
  register int tmc, el, er;
  for (register int i = 1; i <= q; ++i) {
    el = read(), er = read(), tmc = read();
    for (int j = 1; j <= 26; ++j) {
      ton[j] = 0;
    }
    set<node>::iterator itr = split(er + 1), itl = split(el);
    for (set<node>::iterator tm = itl; tm != itr; ++tm) {
      ton[tm->v] += tm->r - tm->l + 1;
    }
    s.erase(itl, itr);
    if (tmc) {
      for (int j = 1; j <= 26; ++j) {
        if (ton[j]) {
          s.insert(node(el, el + ton[j] - 1, j));
          el = el + ton[j];
        }
      }
    } else {
      for (int j = 26; j >= 1; --j) {
        if (ton[j]) {
          s.insert(node(el, el + ton[j] - 1, j));
          el = el + ton[j];
        }
      }
    }
  }
  set<node>::iterator k = s.begin();
  ++k;
  for (set<node>::iterator i = s.begin(); k != s.end(); ++i, ++k)
    for (int j = i->l; j <= i->r; ++j) putchar(i->v ^ 96);
  printf("\n");
  return 0;
}

```