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 <class T>
T abs(T x) {
  return x > 0 ? x : -x;
}
const int N = 400000;
int n;
int m;
char h[100001];
int cnt[N][26];
int x[N];
int y[N];
int z[N];
set<pair<int, int> > all;
int right(int a, int k, int b) {
  if (z[a]) {
    for (int i = 0; i < 26 && k; i++) {
      int tmp = min(cnt[a][i], k);
      cnt[a][i] -= tmp;
      cnt[b][i] += tmp;
      k -= tmp;
    }
  } else {
    for (int i = 25; i >= 0 && k; i--) {
      int tmp = min(cnt[a][i], k);
      cnt[a][i] -= tmp;
      cnt[b][i] += tmp;
      k -= tmp;
    }
  }
  return 0;
}
int left(int a, int k, int b) {
  if (z[a]) {
    for (int i = 25; i >= 0 && k; i--) {
      int tmp = min(cnt[a][i], k);
      cnt[a][i] -= tmp;
      cnt[b][i] += tmp;
      k -= tmp;
    }
  } else {
    for (int i = 0; i < 26 && k; i++) {
      int tmp = min(cnt[a][i], k);
      cnt[a][i] -= tmp;
      cnt[b][i] += tmp;
      k -= tmp;
    }
  }
  return 0;
}
int out() {
  for (auto it = all.begin(); it != all.end(); it++) {
    int j = it->second;
    if (z[j]) {
      for (int k = 25; k >= 0; k--)
        for (int i = 0; i < cnt[j][k]; i++) {
          printf("%c", 'a' + k);
        }
    } else {
      for (int k = 0; k < 26; k++)
        for (int i = 0; i < cnt[j][k]; i++) {
          printf("%c", 'a' + k);
        }
    }
  }
  printf("\n");
  return 0;
}
int main() {
  scanf("%d%d", &n, &m);
  scanf(" %s", h);
  int o = 0;
  for (int i = 0; i < n; i++) {
    all.insert(make_pair(i, o));
    cnt[o][h[i] - 'a']++;
    x[o] = y[o] = i;
    o++;
  }
  for (int i = 0; i < m; i++) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    a--;
    b--;
    c ^= 1;
    auto it = all.lower_bound(make_pair(a, -1));
    if (it != all.begin()) {
      it--;
      int j = it->second;
      if (y[j] >= a) {
        if (y[j] >= b) {
          if (y[j] > b) {
            right(j, y[j] - b, o + 1);
            right(j, b - a + 1, o);
            x[o] = a;
            y[o] = b;
            z[o] = c;
            x[o + 1] = b + 1;
            y[o + 1] = y[j];
            z[o + 1] = z[j];
            y[j] = a - 1;
            all.insert(make_pair(a, o));
            all.insert(make_pair(b + 1, o + 1));
            o += 2;
            continue;
          }
          right(j, b - a + 1, o);
          x[o] = a;
          y[o] = b;
          z[o] = c;
          y[j] = a - 1;
          all.insert(make_pair(a, o));
          o++;
          continue;
        }
        right(j, y[j] - a + 1, o);
        y[j] = a - 1;
      } else {
        it++;
        j = it->second;
        if (y[j] >= b) {
          if (y[j] > b) {
            right(j, y[j] - b, o);
            x[o] = b + 1;
            y[o] = y[j];
            z[o] = z[j];
            all.insert(make_pair(b + 1, o));
            y[j] = b;
            z[j] = c;
            o++;
            continue;
          }
          z[j] = c;
          continue;
        }
        left(j, 1e9, o);
        all.erase(it);
      }
    }
    while (true) {
      auto it = all.lower_bound(make_pair(a, -1));
      if (it == all.end()) break;
      int j = it->second;
      if (x[j] <= b) {
        if (y[j] <= b) {
          left(j, 1e9, o);
          all.erase(it);
        } else {
          left(j, b - x[j] + 1, o);
          all.erase(it);
          x[j] = b + 1;
          all.insert(make_pair(b + 1, j));
          break;
        }
      } else
        break;
    }
    x[o] = a;
    y[o] = b;
    z[o] = c;
    all.insert(make_pair(a, o));
    o++;
  }
  out();
  return 0;
}