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;
const int MOD = 1000000007;
const long long INF = 1e18;
const int MX = 100001;
std::string zodis;
const int lg = 26;
void print(vector<int> a) {
  for (auto u : a) printf("%d ", u);
  printf("\n");
}
void print(int a[]) {
  for (int i = 0; i < lg; ++i) {
    printf("%d ", a[i]);
  }
  printf("\n");
}
struct node {
  int l, r;
  bool asc, desc;
  node *left, *right;
  int val[lg];
  void surink(int a, int b, int (&curr)[lg]) {
    if (l != r) {
      if (asc) make_asc();
      if (desc) make_desc();
    }
    int mid = (l + r) / 2;
    if (a <= l and b >= r) {
      for (int i = 0; i < lg; ++i) {
        curr[i] += val[i];
        val[i] = 0;
      }
      return;
    } else if (b <= mid) {
      left->surink(a, b, curr);
    } else if (a > mid) {
      right->surink(a, b, curr);
    } else {
      left->surink(a, b, curr);
      right->surink(a, b, curr);
    }
    if (l != r)
      for (int i = 0; i < lg; ++i) val[i] = left->val[i] + right->val[i];
  }
  void make_asc() {
    int ls = left->r - left->l + 1;
    int rs = right->r - right->l + 1;
    memset(left->val, 0, sizeof(left->val));
    memset(right->val, 0, sizeof(right->val));
    for (int i = 0; i < lg; ++i) {
      int diff = min(val[i], ls);
      left->val[i] += diff;
      ls -= diff;
      right->val[i] += min(val[i] - diff, rs);
      rs -= min(val[i] - diff, rs);
    }
    asc = false;
    desc = false;
    left->asc = true;
    left->desc = false;
    if (left->l == left->r) left->asc = false;
    right->asc = true;
    right->desc = false;
    if (right->l == right->r) right->asc = false;
  }
  void make_desc() {
    int ls = left->r - left->l + 1;
    int rs = right->r - right->l + 1;
    memset(left->val, 0, sizeof(left->val));
    memset(right->val, 0, sizeof(right->val));
    for (int i = lg - 1; i >= 0; --i) {
      int diff = min(val[i], ls);
      left->val[i] += diff;
      ls -= diff;
      right->val[i] += min(val[i] - diff, rs);
      rs -= min(val[i] - diff, rs);
    }
    asc = false;
    desc = false;
    left->asc = false;
    left->desc = true;
    if (left->l == left->r) left->desc = false;
    right->asc = false;
    right->desc = true;
    if (right->l == right->r) right->desc = false;
  }
  void change(int a, int b, int first, int curr[lg]) {
    int mid = (l + r) / 2;
    if (a <= l && b >= r) {
      for (int i = 0; i < lg; ++i) {
        val[i] = curr[i];
      }
      if (l == r) return;
      if (first) {
        asc = true;
        desc = false;
      } else {
        asc = false;
        desc = true;
      }
      return;
    } else if (b <= mid) {
      left->change(a, b, first, curr);
    } else if (a > mid) {
      right->change(a, b, first, curr);
    } else {
      int ls = mid - max(l, a) + 1;
      int rs = min(b, r) - mid;
      int kair[lg];
      int des[lg];
      memset(kair, 0, sizeof(kair));
      memset(des, 0, sizeof(des));
      if (first) {
        for (int i = 0; i < lg; ++i) {
          int diff = min(curr[i], ls);
          kair[i] += diff;
          ls -= diff;
          des[i] += min(curr[i] - diff, rs);
          rs -= min(curr[i] - diff, rs);
        }
      } else {
        for (int i = lg - 1; i >= 0; --i) {
          int diff = min(curr[i], ls);
          kair[i] += diff;
          ls -= diff;
          des[i] += min(curr[i] - diff, rs);
          rs -= min(curr[i] - diff, rs);
        }
      }
      left->change(a, b, first, kair);
      right->change(a, b, first, des);
    }
    for (int i = 0; i < lg; ++i) {
      val[i] = left->val[i] + right->val[i];
    }
  }
  void finish() {
    if (l == r) {
      for (int i = 0; i < lg; ++i) {
        if (val[i]) {
          zodis[l - 1] = char(i + 'a');
          return;
        }
      }
    }
    if (desc) make_desc();
    if (asc) make_asc();
    left->finish();
    right->finish();
  }
  node(int a, int b) {
    l = a;
    r = b;
    asc = false;
    desc = false;
    memset(val, 0, sizeof(val));
    if (a != b) {
      left = new node(a, (a + b) / 2);
      right = new node((a + b) / 2 + 1, b);
      for (int i = 0; i < lg; ++i) val[i] = left->val[i] + right->val[i];
    } else {
      val[zodis[a - 1] - 'a']++;
    }
  }
};
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int N, Q;
  cin >> N >> Q >> zodis;
  int a, b, first;
  node medis(1, N);
  int pivot[lg];
  for (int i = 0; i < Q; ++i) {
    cin >> a >> b >> first;
    if (a == b) continue;
    memset(pivot, 0, sizeof(pivot));
    medis.surink(a, b, pivot);
    medis.change(a, b, (int)first, pivot);
  }
  medis.finish();
  cout << zodis << '\n';
}