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>

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
using max_pq = priority_queue<T>;
const int inf = 2e9 + 5;
const long long l_inf = 2e18 + 5;
const int mod_v = 1e9 + 7;
const int max_n = 1e5 + 5;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
template <typename T>
T gcd(T a, T b) {
  while (b) {
    T temp = a % b;
    a = b;
    b = temp;
  }
  return a;
}
template <typename T>
tuple<T, T, T> egcd(T a, T b) {
  T x1 = 1, x2 = 0, y1 = 0, y2 = 1;
  while (b) {
    T q = a / b, r = a % b;
    T new_x = x1 - q * x2, new_y = y1 - q * y2;
    x1 = x2, y1 = y2, x2 = new_x, y2 = new_y;
    a = b, b = r;
  }
  return make_tuple(a, x1, y1);
}
inline long long lcm(long long a, long long b) { return a * b / gcd(a, b); }
template <typename T>
inline T mod(T a, T b = mod_v) {
  return (a % b + b) % b;
}
template <typename T>
inline T mod_inv(T a, T b = mod_v) {
  return mod(get<1>(egcd(a, b)), b);
}
template <typename T>
inline T sum(T a, T b, T m = mod_v) {
  return mod(mod(a, m) + mod(b, m), m);
}
template <typename T>
inline T difference(T a, T b, T m = mod_v) {
  return mod(mod(a, m) - mod(b, m), m);
}
inline long long product(long long a, long long b, long long m = mod_v) {
  return mod(mod(a, m) * mod(b, m), m);
}
inline long long quotient(long long a, long long b, long long m = mod_v) {
  return mod(mod(a, m) * mod_inv(b, m), m);
}
template <typename T, typename T2>
ostream &operator<<(ostream &s, const pair<T, T2> &p) {
  return s << p.first << ' ' << p.second << ' ';
}
template <typename T, typename T2>
istream &operator>>(istream &s, pair<T, T2> &p) {
  return s >> p.first >> p.second;
}
template <typename T>
ostream &operator<<(ostream &s, const vector<T> &v) {
  for (auto it : v) s << it << ' ';
  return s;
}
template <typename T>
istream &operator>>(istream &s, vector<T> &v) {
  for (auto it = (v).begin(), it_ = (v).end(); it != it_; ++it) s >> *it;
  return s;
}
template <typename T>
void read_range(T beg, T end) {
  while (beg != end) cin >> *beg++;
}
template <typename T>
void print_range(T beg, T end) {
  while (beg != end) cout << *beg++ << ' ';
}
struct reader {
  template <typename T>
  reader &operator,(T &v) {
    cin >> v;
    return *this;
  }
} rdr;
struct debugger {
  template <typename T>
  debugger &operator,(const T &v) {
    cerr << v << ", ";
    return *this;
  }
} dbg;
int n, q;
string s;
int st[26][4 * max_n], lazy[26][4 * max_n], cnt[26];
void build(int c, int i = 1, int l = 1, int r = n) {
  if (l == r) {
    st[c][i] = (s[l] == c + 'a' ? 1 : 0);
    return;
  }
  build(c, (2 * (i)), l, (((l) + (r)) / 2));
  build(c, (2 * (i) + 1), (((l) + (r)) / 2) + 1, r);
  st[c][i] = st[c][(2 * (i))] + st[c][(2 * (i) + 1)];
}
void propagate(int c, int i, int l, int r) {
  if (lazy[c][i]) {
    if (lazy[c][i] == 1)
      st[c][i] = r - l + 1;
    else {
      st[c][i] = 0;
    }
    if (l != r) lazy[c][(2 * (i))] = lazy[c][(2 * (i) + 1)] = lazy[c][i];
    lazy[c][i] = 0;
  }
}
void update(int x, int y, int c, int type, int i = 1, int l = 1, int r = n) {
  if (x == l and r == y) {
    lazy[c][i] = type;
    propagate(c, i, l, r);
    return;
  }
  propagate(c, i, l, r);
  int md = (((l) + (r)) / 2), li = (2 * (i)), ri = (2 * (i) + 1);
  if (x > md) {
    update(x, y, c, type, ri, md + 1, r);
    propagate(c, li, l, md);
  } else if (y <= md) {
    update(x, y, c, type, li, l, md);
    propagate(c, ri, md + 1, r);
  } else {
    update(x, md, c, type, li, l, md);
    update(md + 1, y, c, type, ri, md + 1, r);
  }
  st[c][i] = st[c][li] + st[c][ri];
}
int query(int x, int y, int c, int i = 1, int l = 1, int r = n) {
  propagate(c, i, l, r);
  if (x == l and r == y) return st[c][i];
  int md = (((l) + (r)) / 2), li = (2 * (i)), ri = (2 * (i) + 1);
  if (x > md) return query(x, y, c, ri, md + 1, r);
  if (y <= md) return query(x, y, c, li, l, md);
  int lres = query(x, md, c, li, l, md);
  int rres = query(md + 1, y, c, ri, md + 1, r);
  return lres + rres;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> q;
  string t;
  rdr, t;
  ;
  s = '0' + t;
  for (int i = 0; i < 26; ++i) build(i);
  for (int i = 0, i_ = (q); i < i_; ++i) {
    int x, y, asc;
    rdr, x, y, asc;
    ;
    int st = 25, ed = -1, inc = -1;
    if (asc) st = 0, ed = 26, inc = 1;
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < 26; ++i) cnt[i] = query(x, y, i);
    int pos = x;
    for (int i = st; i != ed; i += inc)
      if (cnt[i]) {
        update(x, y, i, 2);
        update(pos, pos + cnt[i] - 1, i, 1);
        pos += cnt[i];
      }
  }
  for (int i = 1; i <= n; ++i) {
    int j;
    for (j = 0; j < 26; ++j)
      if (query(i, i, j)) break;
    cout << (char)('a' + j);
  }
  return 0;
}