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>
const int INF = 1e9;
const long long lINF = 1e18;
const double EPS = 1e-10;
using namespace std;
const int N = 1e5 + 100;
struct segm {
  vector<int> sum, change, changed;
  segm(int n = 0) {
    sum.resize(n * 4);
    change.resize(n * 4);
    changed.resize(n * 4);
  }
  void push(int v, int vl, int vr) {
    if (changed[v]) {
      changed[v * 2 + 1] = 1;
      changed[v * 2 + 2] = 1;
      change[v * 2 + 1] = change[v * 2 + 2] = change[v];
      int mid = (vl + vr) / 2;
      sum[v * 2 + 1] = change[v] * (mid - vl);
      sum[v * 2 + 2] = change[v] * (vr - mid);
      changed[v] = 0;
    }
  }
  void upd(int v, int vl, int vr, int l, int r, int x) {
    if (vl >= r || vr <= l) {
      return;
    }
    if (vl >= l && vr <= r) {
      change[v] = x;
      changed[v] = 1;
      sum[v] = (vr - vl) * x;
    } else {
      push(v, vl, vr);
      int mid = (vl + vr) / 2;
      upd(v * 2 + 1, vl, mid, l, r, x);
      upd(v * 2 + 2, mid, vr, l, r, x);
      sum[v] = sum[v * 2 + 1] + sum[v * 2 + 2];
    }
  }
  int get(int v, int vl, int vr, int l, int r) {
    if (vl >= r || vr <= l) {
      return 0;
    }
    if (vl >= l && vr <= r) {
      return sum[v];
    } else {
      if (changed[v]) {
        return change[v] * (min(r, vr) - max(l, vl));
      }
      int mid = (vl + vr) / 2;
      return get(v * 2 + 1, vl, mid, l, r) + get(v * 2 + 2, mid, vr, l, r);
    }
  }
  void print(int v, int vl, int vr, vector<int>& vec) {
    if (changed[v]) {
      for (int i = vl; i < vr; i++) {
        vec.push_back(change[v]);
      }
    } else {
      if (vr == vl + 1) {
        vec.push_back(0);
      } else {
        int mid = (vl + vr) / 2;
        print(v + v + 1, vl, mid, vec);
        print(v + v + 2, mid, vr, vec);
      }
    }
  }
};
vector<segm> segms;
vector<int> ans[26];
int n, q;
char s[N];
int main() {
  scanf("%d%d", &n, &q);
  for (int i = 0; i < 26; i++) {
    segms.push_back(segm(n));
  }
  scanf(" %s", s);
  for (int i = 0; i < n; i++) {
    segms[s[i] - 'a'].upd(0, 0, n, i, i + 1, 1);
  }
  for (int num = 0; num < q; num++) {
    int i, j, k;
    scanf("%d%d%d", &i, &j, &k);
    i--, j--;
    vector<int> cnt(26);
    for (int r = 0; r < 26; r++) {
      cnt[r] = segms[r].get(0, 0, n, i, j + 1);
    }
    if (k == 1) {
      for (int w = i, r = 0; r < 26; r++) {
        if (cnt[r]) {
          segms[r].upd(0, 0, n, i, j + 1, 0);
          segms[r].upd(0, 0, n, w, w + cnt[r], 1);
          w += cnt[r];
        }
      }
    } else {
      for (int w = i, r = 25; r >= 0; r--) {
        if (cnt[r]) {
          segms[r].upd(0, 0, n, i, j + 1, 0);
          segms[r].upd(0, 0, n, w, w + cnt[r], 1);
          w += cnt[r];
        }
      }
    }
  }
  for (int i = 0; i < 26; i++) {
    segms[i].print(0, 0, n, ans[i]);
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 26; j++) {
      if (ans[j][i]) {
        printf("%c", j + 'a');
      }
    }
  }
  printf("\n");
  return 0;
}