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 mul(long long a, long long b) { return (a * b) % (100000007); }
long long add(long long a, long long b) { return (a + b) % (100000007); }
long long sub(long long a, long long b) {
  return (a - b + (a - b) / (100000007) * (100000007) + (100000007)) %
         (100000007);
}
void upd(long long &a, long long b) {
  a = (a % (100000007) + b % (100000007)) % (100000007);
}
int n, q;
int l, r, v, _ans;
class Stree {
 public:
  int mark[(400000 + 10)], tree[(400000 + 10)];
  Stree() {
    memset(mark, 0, sizeof(mark));
    memset(tree, 0, sizeof(tree));
  }
  void pushdown(int o, int L, int R) {
    if (L < R)
      if (mark[o]) mark[(o << 1)] = mark[((o << 1) + 1)] = mark[o], mark[o] = 0;
  }
  void maintain(int o, int L, int R) {
    if (mark[o])
      tree[o] = (R - L + 1) * (mark[o] - 1);
    else if (L < R)
      tree[o] = tree[(o << 1)] + tree[((o << 1) + 1)];
  }
  void set(int o, int L, int R) {
    if (l <= L && R <= r) {
      mark[o] = v;
      maintain(o, L, R);
      return;
    }
    pushdown(o, L, R);
    int M = (L + R) >> 1;
    if (l <= M)
      set((o << 1), L, M);
    else
      maintain((o << 1), L, M);
    if (M < r)
      set(((o << 1) + 1), M + 1, R);
    else
      maintain(((o << 1) + 1), M + 1, R);
    maintain(o, L, R);
  }
  void get_sum(int o, int L, int R) {
    if (l <= L && R <= r) {
      _ans += tree[o];
      return;
    }
    if (mark[o]) {
      _ans += (min(r, R) - max(L, l) + 1) * (mark[o] - 1);
      return;
    }
    int M = (L + R) >> 1;
    if (l <= M) get_sum((o << 1), L, M);
    if (M < r) get_sum(((o << 1) + 1), M + 1, R);
  }
} S[26];
char s[(400000 + 10)];
int cnt[26] = {0};
int main() {
  scanf("%d%d%s", &n, &q, s);
  for (int i = 0; i < n; i++) {
    l = r = i + 1, v = 2;
    S[s[i] - 'a'].set(1, 1, n);
  }
  for (int qcase = 1; qcase <= q; qcase++) {
    int b;
    scanf("%d%d%d", &l, &r, &b);
    v = 1;
    for (int i = 0; i < 26; i++) {
      _ans = 0;
      S[i].get_sum(1, 1, n);
      cnt[i] = _ans;
      S[i].set(1, 1, n);
    }
    v = 2;
    if (b) {
      for (int i = 0; i < 26; i++) {
        if (!cnt[i]) continue;
        r = l + cnt[i] - 1;
        S[i].set(1, 1, n);
        l = r + 1;
      }
    } else {
      for (int i = 0; i < 26; i++) {
        if (!cnt[i]) continue;
        l = r - cnt[i] + 1;
        S[i].set(1, 1, n);
        r = l - 1;
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < 26; j++) {
      l = r = i;
      _ans = 0;
      S[j].get_sum(1, 1, n);
      if (_ans) {
        s[i - 1] = 'a' + j;
        break;
      }
    }
  }
  printf("%s\n", s);
  return 0;
}