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;
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
class SegTree {
 public:
  int arr[100010], tree[400010], lazy[400010];
  void build(int low, int high, int pos) {
    int mid = (low + high) >> 1;
    if (low == high)
      tree[pos] = arr[mid];
    else {
      build(low, mid, 2 * pos + 1);
      build(mid + 1, high, 2 * pos + 2);
      tree[pos] = tree[2 * pos + 1] + tree[2 * pos + 2];
    }
  }
  void update(int low, int high, int pos, int qLow, int qHigh, int x) {
    int mid = (low + high) >> 1;
    if (low > high) return;
    if (lazy[pos] != -1) {
      tree[pos] = (high - low + 1) * lazy[pos];
      if (low != high) lazy[2 * pos + 1] = lazy[2 * pos + 2] = lazy[pos];
      lazy[pos] = -1;
    }
    if (qLow > high || qHigh < low)
      return;
    else if (qLow <= low && qHigh >= high) {
      tree[pos] = (high - low + 1) * x;
      if (low != high) lazy[2 * pos + 1] = lazy[2 * pos + 2] = x;
    } else {
      update(low, mid, 2 * pos + 1, qLow, qHigh, x);
      update(mid + 1, high, 2 * pos + 2, qLow, qHigh, x);
      tree[pos] = tree[2 * pos + 1] + tree[2 * pos + 2];
    }
  }
  int query(int low, int high, int pos, int qLow, int qHigh) {
    int mid = (low + high) >> 1;
    if (lazy[pos] != -1) {
      tree[pos] = (high - low + 1) * lazy[pos];
      if (low != high) lazy[2 * pos + 1] = lazy[2 * pos + 2] = lazy[pos];
      lazy[pos] = -1;
    }
    if (qLow > high || qHigh < low)
      return 0;
    else if (qLow <= low && qHigh >= high)
      return tree[pos];
    else
      return query(low, mid, 2 * pos + 1, qLow, qHigh) +
             query(mid + 1, high, 2 * pos + 2, qLow, qHigh);
  }
};
SegTree t[26];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int n, q;
  cin >> n >> q;
  string str;
  cin >> str;
  for (int i = 0; i < (n); ++i) ++(t[str[i] - 97].arr[i]);
  for (int i = 0; i < (26); ++i) {
    for (int j = 0; j < (400010); ++j) t[i].lazy[j] = -1;
    t[i].build(0, n - 1, 0);
  }
  while (q--) {
    int l, r, x;
    cin >> l >> r >> x;
    --l;
    --r;
    if (x) {
      int curL = l;
      for (int i = 0; i < (26); ++i) {
        int sum = t[i].query(0, n - 1, 0, l, r);
        t[i].update(0, n - 1, 0, l, curL - 1, 0);
        t[i].update(0, n - 1, 0, curL, curL + sum - 1, 1);
        t[i].update(0, n - 1, 0, curL + sum, r, 0);
        curL = curL + sum;
      }
    } else {
      int curL = l;
      for (int i = (25); i >= (0); --i) {
        int sum = t[i].query(0, n - 1, 0, l, r);
        t[i].update(0, n - 1, 0, l, curL - 1, 0);
        t[i].update(0, n - 1, 0, curL, curL + sum - 1, 1);
        t[i].update(0, n - 1, 0, curL + sum, r, 0);
        curL = curL + sum;
      }
    }
  }
  string ans = "";
  for (int i = 0; i < (n); ++i)
    for (int j = 0; j < (26); ++j)
      if (t[j].query(0, n - 1, 0, i, i)) {
        ans += (char)(j + 97);
        break;
      }
  cout << ans << '\n';
  return 0;
}