#include <bits/stdc++.h>
using namespace std;
template <class T>
T __sqr(const T x) {
  return x * x;
}
template <class T, class X>
inline T __pow(T a, X y) {
  T z = 1;
  for (int i = 1; i <= y; i++) {
    z *= a;
  }
  return z;
}
template <class T>
inline T gcd(T a, T b) {
  a = abs(a);
  b = abs(b);
  if (!b) return a;
  return __gcd(b, a % b);
}
template <class T>
inline T lcm(T a, T b) {
  a = abs(a);
  b = abs(b);
  return (a / __gcd(a, b)) * b;
}
inline bool ispow2(int x) { return (x != 0 && (x & (x - 1)) == 0); }
template <class T>
void UpdateMin(T &x, T y) {
  if (y < x) {
    x = y;
  }
}
template <class T>
void UpdateMax(T &x, T y) {
  if (x < y) {
    x = y;
  }
}
template <class T, class X, class Y>
inline T bigmod(T n, X m, Y mod) {
  unsigned long long ret = 1, a = n % mod;
  while (m) {
    if (m & 1) ret = (ret * a) % mod;
    m >>= 1;
    a = (a * a) % mod;
  }
  ret %= mod;
  return (T)ret;
}
template <class T, class Y>
inline T modinv(T n, Y mod) {
  return bigmod(n, mod - 2, mod);
}
template <class T, class X>
int getbit(T s, X i) {
  return (s >> i) & 1;
}
template <class T, class X>
T onbit(T s, X i) {
  return s | (T(1) << i);
}
template <class T, class X>
T offbit(T s, X i) {
  return s & (~(T(1) << i));
}
template <class T>
inline void read(T &n) {
  char c;
  for (c = getchar(); !(c >= '0' && c <= '9'); c = getchar())
    ;
  n = c - '0';
  for (c = getchar(); c >= '0' && c <= '9'; c = getchar()) n = n * 10 + c - '0';
}
void extended_euclid(long long a, long long b, long long &x, long long &y) {
  if (!b) {
    x = 1, y = 0;
    return;
  }
  long long first, second;
  extended_euclid(b, a % b, first, second);
  x = second;
  y = first - (a / b) * second;
}
pair<long long, pair<long long, long long> > extendedEuclid(long long a,
                                                            long long b) {
  long long x = 1, y = 0;
  long long xLast = 0, yLast = 1;
  long long q, r, m, n;
  while (a != 0) {
    q = b / a;
    r = b % a;
    m = xLast - q * x;
    n = yLast - q * y;
    xLast = x, yLast = y;
    x = m, y = n;
    b = a, a = r;
  }
  return make_pair(b, make_pair(xLast, yLast));
}
const long long mod[] = {0,          1000000007, 1000000009,
                         1000000021, 1000000033, 1000000097,
                         1000000093, 1000000097, 1000000103};
const long long base[] = {0,       1000003, 1000033, 1000037, 1000039,
                          1000081, 1000099, 1000117, 1000121};
char str[(100000 + 20)];
int node[30][4 * (100000 + 20)];
int lazy[30][4 * (100000 + 20)];
void build(int id, int s, int e) {
  if (s == e) {
    for (int i = 1; i <= 26; i++) {
      int ch = i;
      node[ch][id] = ((str[s] - 'a' + 1) == ch);
      ;
    }
    return;
  }
  int m = (s + e) / 2;
  int lf = 2 * id, rg = 2 * id + 1;
  build(lf, s, m);
  build(rg, m + 1, e);
  for (int i = 1; i <= 26; i++) {
    int ch = i;
    node[ch][id] = node[ch][lf] + node[ch][rg];
  }
}
void update_lazy(int ch, int id, int s, int m, int e, int lf, int rg) {
  if (s == e) return;
  node[ch][lf] = (node[ch][id] ? (m - s + 1) : 0);
  node[ch][rg] = (node[ch][id] ? (e - (m + 1) + 1) : 0);
  lazy[ch][id] = 0;
  lazy[ch][lf] = lazy[ch][rg] = 1;
}
int query(int ch, int id, int s, int e, int st, int ed) {
  if (ed < st) return 0;
  if (s == st && e == ed) return node[ch][id];
  int m = (s + e) / 2;
  int lf = 2 * id, rg = 2 * id + 1;
  if (lazy[ch][id]) update_lazy(ch, id, s, m, e, lf, rg);
  int ret;
  if (ed <= m) {
    ret = query(ch, lf, s, m, st, ed);
  } else if (st > m) {
    ret = query(ch, rg, m + 1, e, st, ed);
  } else {
    int r1 = query(ch, lf, s, m, st, m);
    int r2 = query(ch, rg, m + 1, e, m + 1, ed);
    ret = r1 + r2;
  }
  return ret;
}
void update(int ch, int id, int s, int e, int st, int ed, int val) {
  if (ed < st) return;
  if (s == st && e == ed) {
    node[ch][id] = val * (e - s + 1);
    lazy[ch][id] = 1;
    return;
  }
  int m = (s + e) / 2;
  int lf = 2 * id, rg = 2 * id + 1;
  if (lazy[ch][id]) update_lazy(ch, id, s, m, e, lf, rg);
  if (ed <= m)
    update(ch, lf, s, m, st, ed, val);
  else if (st > m)
    update(ch, rg, m + 1, e, st, ed, val);
  else {
    update(ch, lf, s, m, st, m, val);
    update(ch, rg, m + 1, e, m + 1, ed, val);
  }
  node[ch][id] = node[ch][lf] + node[ch][rg];
}
int n, q;
void res() {
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= 26; j++) {
      if (query(j, 1, 1, n, i, i)) {
        printf("%c", 'a' + j - 1);
        break;
      }
    }
  }
  puts("");
}
int main() {
  scanf("%d%d", &n, &q);
  scanf("%s", str + 1);
  build(1, 1, n);
  int x, y, tp;
  for (int i = 1; i <= q; i++) {
    scanf("%d%d%d", &x, &y, &tp);
    int tot = 0;
    for (int j = 1; j <= 26; j++) {
      int ch = j;
      int q = query(ch, 1, 1, n, x, y);
      update(ch, 1, 1, n, x, y, 0);
      if (tp)
        update(ch, 1, 1, n, x + tot, x + tot + q - 1, 1);
      else
        update(ch, 1, 1, n, y - tot - q + 1, y - tot, 1);
      tot += q;
    }
  }
  res();
  return 0;
}

### 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;
template <class T>
T __sqr(const T x) {
  return x * x;
}
template <class T, class X>
inline T __pow(T a, X y) {
  T z = 1;
  for (int i = 1; i <= y; i++) {
    z *= a;
  }
  return z;
}
template <class T>
inline T gcd(T a, T b) {
  a = abs(a);
  b = abs(b);
  if (!b) return a;
  return __gcd(b, a % b);
}
template <class T>
inline T lcm(T a, T b) {
  a = abs(a);
  b = abs(b);
  return (a / __gcd(a, b)) * b;
}
inline bool ispow2(int x) { return (x != 0 && (x & (x - 1)) == 0); }
template <class T>
void UpdateMin(T &x, T y) {
  if (y < x) {
    x = y;
  }
}
template <class T>
void UpdateMax(T &x, T y) {
  if (x < y) {
    x = y;
  }
}
template <class T, class X, class Y>
inline T bigmod(T n, X m, Y mod) {
  unsigned long long ret = 1, a = n % mod;
  while (m) {
    if (m & 1) ret = (ret * a) % mod;
    m >>= 1;
    a = (a * a) % mod;
  }
  ret %= mod;
  return (T)ret;
}
template <class T, class Y>
inline T modinv(T n, Y mod) {
  return bigmod(n, mod - 2, mod);
}
template <class T, class X>
int getbit(T s, X i) {
  return (s >> i) & 1;
}
template <class T, class X>
T onbit(T s, X i) {
  return s | (T(1) << i);
}
template <class T, class X>
T offbit(T s, X i) {
  return s & (~(T(1) << i));
}
template <class T>
inline void read(T &n) {
  char c;
  for (c = getchar(); !(c >= '0' && c <= '9'); c = getchar())
    ;
  n = c - '0';
  for (c = getchar(); c >= '0' && c <= '9'; c = getchar()) n = n * 10 + c - '0';
}
void extended_euclid(long long a, long long b, long long &x, long long &y) {
  if (!b) {
    x = 1, y = 0;
    return;
  }
  long long first, second;
  extended_euclid(b, a % b, first, second);
  x = second;
  y = first - (a / b) * second;
}
pair<long long, pair<long long, long long> > extendedEuclid(long long a,
                                                            long long b) {
  long long x = 1, y = 0;
  long long xLast = 0, yLast = 1;
  long long q, r, m, n;
  while (a != 0) {
    q = b / a;
    r = b % a;
    m = xLast - q * x;
    n = yLast - q * y;
    xLast = x, yLast = y;
    x = m, y = n;
    b = a, a = r;
  }
  return make_pair(b, make_pair(xLast, yLast));
}
const long long mod[] = {0,          1000000007, 1000000009,
                         1000000021, 1000000033, 1000000097,
                         1000000093, 1000000097, 1000000103};
const long long base[] = {0,       1000003, 1000033, 1000037, 1000039,
                          1000081, 1000099, 1000117, 1000121};
char str[(100000 + 20)];
int node[30][4 * (100000 + 20)];
int lazy[30][4 * (100000 + 20)];
void build(int id, int s, int e) {
  if (s == e) {
    for (int i = 1; i <= 26; i++) {
      int ch = i;
      node[ch][id] = ((str[s] - 'a' + 1) == ch);
      ;
    }
    return;
  }
  int m = (s + e) / 2;
  int lf = 2 * id, rg = 2 * id + 1;
  build(lf, s, m);
  build(rg, m + 1, e);
  for (int i = 1; i <= 26; i++) {
    int ch = i;
    node[ch][id] = node[ch][lf] + node[ch][rg];
  }
}
void update_lazy(int ch, int id, int s, int m, int e, int lf, int rg) {
  if (s == e) return;
  node[ch][lf] = (node[ch][id] ? (m - s + 1) : 0);
  node[ch][rg] = (node[ch][id] ? (e - (m + 1) + 1) : 0);
  lazy[ch][id] = 0;
  lazy[ch][lf] = lazy[ch][rg] = 1;
}
int query(int ch, int id, int s, int e, int st, int ed) {
  if (ed < st) return 0;
  if (s == st && e == ed) return node[ch][id];
  int m = (s + e) / 2;
  int lf = 2 * id, rg = 2 * id + 1;
  if (lazy[ch][id]) update_lazy(ch, id, s, m, e, lf, rg);
  int ret;
  if (ed <= m) {
    ret = query(ch, lf, s, m, st, ed);
  } else if (st > m) {
    ret = query(ch, rg, m + 1, e, st, ed);
  } else {
    int r1 = query(ch, lf, s, m, st, m);
    int r2 = query(ch, rg, m + 1, e, m + 1, ed);
    ret = r1 + r2;
  }
  return ret;
}
void update(int ch, int id, int s, int e, int st, int ed, int val) {
  if (ed < st) return;
  if (s == st && e == ed) {
    node[ch][id] = val * (e - s + 1);
    lazy[ch][id] = 1;
    return;
  }
  int m = (s + e) / 2;
  int lf = 2 * id, rg = 2 * id + 1;
  if (lazy[ch][id]) update_lazy(ch, id, s, m, e, lf, rg);
  if (ed <= m)
    update(ch, lf, s, m, st, ed, val);
  else if (st > m)
    update(ch, rg, m + 1, e, st, ed, val);
  else {
    update(ch, lf, s, m, st, m, val);
    update(ch, rg, m + 1, e, m + 1, ed, val);
  }
  node[ch][id] = node[ch][lf] + node[ch][rg];
}
int n, q;
void res() {
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= 26; j++) {
      if (query(j, 1, 1, n, i, i)) {
        printf("%c", 'a' + j - 1);
        break;
      }
    }
  }
  puts("");
}
int main() {
  scanf("%d%d", &n, &q);
  scanf("%s", str + 1);
  build(1, 1, n);
  int x, y, tp;
  for (int i = 1; i <= q; i++) {
    scanf("%d%d%d", &x, &y, &tp);
    int tot = 0;
    for (int j = 1; j <= 26; j++) {
      int ch = j;
      int q = query(ch, 1, 1, n, x, y);
      update(ch, 1, 1, n, x, y, 0);
      if (tp)
        update(ch, 1, 1, n, x + tot, x + tot + q - 1, 1);
      else
        update(ch, 1, 1, n, y - tot - q + 1, y - tot, 1);
      tot += q;
    }
  }
  res();
  return 0;
}

```