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;
long long n, q;
string a;
long long seg[4 * 100005][30], lazy[4 * 100005][30], cnt[30];
void build(long long cur, long long st, long long end) {
  if (st == end) {
    seg[cur][a[st] - 'a'] = 1;
    for (long long int j = 0; j < 26; j++) lazy[cur][j] = -1;
    return;
  }
  long long mid = (st + end) >> 1;
  build(2 * cur, st, mid);
  build(2 * cur + 1, mid + 1, end);
  for (long long int j = 0; j < 26; j++) {
    lazy[cur][j] = -1;
    seg[cur][j] = seg[2 * cur][j] + seg[2 * cur + 1][j];
  }
}
void updaterange(long long cur, long long st, long long end, long long l,
                 long long r, long long val, long long j) {
  if (lazy[cur][j] != -1) {
    seg[cur][j] = (end - st + 1) * lazy[cur][j];
    if (st != end) {
      lazy[2 * cur][j] = lazy[cur][j];
      lazy[2 * cur + 1][j] = lazy[cur][j];
    }
    lazy[cur][j] = -1;
  }
  if (st > end || st > r || end < l) return;
  if (l <= st && end <= r) {
    seg[cur][j] = (end - st + 1) * val;
    if (st != end) {
      lazy[2 * cur][j] = val;
      lazy[2 * cur + 1][j] = val;
    }
    lazy[cur][j] = -1;
    return;
  }
  long long mid = (st + end) >> 1;
  updaterange(2 * cur, st, mid, l, r, val, j);
  updaterange(2 * cur + 1, mid + 1, end, l, r, val, j);
  seg[cur][j] = seg[2 * cur][j] + seg[2 * cur + 1][j];
}
long long query(long long cur, long long st, long long end, long long l,
                long long r, long long j) {
  if (st > end || st > r || end < l) return 0;
  if (lazy[cur][j] != -1) {
    seg[cur][j] = (end - st + 1) * lazy[cur][j];
    if (st != end) {
      lazy[2 * cur][j] = lazy[cur][j];
      lazy[2 * cur + 1][j] = lazy[cur][j];
    }
    lazy[cur][j] = -1;
  }
  if (st >= l && end <= r) return seg[cur][j];
  long long mid = (st + end) >> 1;
  long long ans1 = query(2 * cur, st, mid, l, r, j);
  long long ans2 = query(2 * cur + 1, mid + 1, end, l, r, j);
  return ans1 + ans2;
}
void get(long long cur, long long st, long long end, long long j) {
  if (lazy[cur][j] != -1) {
    seg[cur][j] = lazy[cur][j] * (end - st + 1);
    if (st != end) {
      lazy[2 * cur][j] = lazy[cur][j];
      lazy[2 * cur + 1][j] = lazy[cur][j];
    }
    lazy[cur][j] = -1;
  }
  if (!seg[cur][j]) return;
  if (st == end) {
    a[st] = j + 'a';
    return;
  }
  long long mid = (st + end) >> 1;
  get(2 * cur, st, mid, j);
  get(2 * cur + 1, mid + 1, end, j);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int TESTS = 1;
  while (TESTS--) {
    long long n, q;
    cin >> n >> q;
    cin >> a;
    build(1, 0, n - 1);
    while (q--) {
      long long x, y, up;
      cin >> x >> y >> up;
      x--;
      y--;
      for (long long int j = 0; j < 26; j++)
        cnt[j] = query(1, 0, n - 1, x, y, j);
      long long cur = x;
      if (!up) cur = y;
      for (long long int j = 0; j < 26; j++) {
        if (!cnt[j]) continue;
        updaterange(1, 0, n - 1, x, y, 0, j);
        if (up) {
          updaterange(1, 0, n - 1, cur, cur + cnt[j] - 1, 1, j);
          cur += cnt[j];
        } else {
          updaterange(1, 0, n - 1, cur - cnt[j] + 1, cur, 1, j);
          cur -= cnt[j];
        }
      }
    }
    for (long long int i = 0; i < 26; i++) get(1, 0, n - 1, i);
    cout << a;
  }
  return 0;
}