#include <bits/stdc++.h>
using namespace std;
long long segTree[26][400005];
long long arr[100005];
long long lazy[26][400005];
long long n, m, t, l, r, x;
void Build(long long pos, long long low, long long high, long long bit) {
  if (low == high) {
    segTree[bit][pos] = (arr[low] == bit ? 1 : 0);
    return;
  }
  long long mid = (low + high) / 2;
  Build(2 * pos + 1, low, mid, bit);
  Build(2 * pos + 2, mid + 1, high, bit);
  segTree[bit][pos] = (segTree[bit][2 * pos + 1] + segTree[bit][2 * pos + 2]);
}
long long RangeQuery(long long pos, long long low, long long high,
                     long long qlow, long long qhigh, long long bit) {
  if (low > high) return 0;
  if (lazy[bit][pos] != -1) {
    if (low != high) {
      lazy[bit][2 * pos + 1] = lazy[bit][pos];
      lazy[bit][2 * pos + 2] = lazy[bit][pos];
    }
    segTree[bit][pos] = lazy[bit][pos] * (high - low + 1);
    lazy[bit][pos] = -1;
  }
  if (qlow <= low && qhigh >= high) return segTree[bit][pos];
  if (qlow > high || qhigh < low) return 0;
  long long mid = (low + high) / 2;
  long long a = RangeQuery(2 * pos + 1, low, mid, qlow, qhigh, bit);
  long long b = RangeQuery(2 * pos + 2, mid + 1, high, qlow, qhigh, bit);
  return (a + b);
}
void update(long long pos, long long low, long long high, long long ulow,
            long long uhigh, long long ch, long long ff) {
  if (low > high) return;
  if (lazy[ch][pos] != -1) {
    segTree[ch][pos] = lazy[ch][pos] * (high - low + 1);
    if (low != high) {
      lazy[ch][2 * pos + 1] = lazy[ch][pos];
      lazy[ch][2 * pos + 2] = lazy[ch][pos];
    }
    lazy[ch][pos] = -1;
  }
  if (ulow > high || uhigh < low) return;
  if (ulow <= low && uhigh >= high) {
    if (low != high) {
      lazy[ch][2 * pos + 1] = ff;
      lazy[ch][2 * pos + 2] = ff;
      segTree[ch][pos] = ff * (high - low + 1);
    } else
      segTree[ch][pos] = ff;
    lazy[ch][pos] = -1;
    return;
  }
  long long mid = (low + high) / 2;
  update(2 * pos + 1, low, mid, ulow, uhigh, ch, ff);
  update(2 * pos + 2, mid + 1, high, ulow, uhigh, ch, ff);
  segTree[ch][pos] = segTree[ch][2 * pos + 1] + segTree[ch][2 * pos + 2];
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  memset(lazy, -1, sizeof(lazy));
  cin >> n >> m;
  string str;
  cin >> str;
  for (long long i = 0; i < n; i++) arr[i] = (str[i] - 'a');
  for (long long i = 0; i < 26; i++) Build(0, 0, n - 1, i);
  while (m--) {
    cin >> l >> r >> t;
    l--;
    r--;
    long long freq[26];
    memset(freq, 0, sizeof(freq));
    for (long long i = 0; i < 26; i++)
      freq[i] = RangeQuery(0, 0, n - 1, l, r, i);
    if (t == 0) {
      long long st = l;
      for (long long i = 25; i >= 0; i--) {
        if (freq[i]) {
          update(0, 0, n - 1, l, r, i, 0);
          update(0, 0, n - 1, st, st + freq[i] - 1, i, 1);
          st = st + freq[i];
        }
      }
    } else {
      long long st = l;
      for (long long i = 0; i < 26; i++) {
        if (freq[i]) {
          update(0, 0, n - 1, l, r, i, 0);
          update(0, 0, n - 1, st, st + freq[i] - 1, i, 1);
          st = st + freq[i];
        }
      }
    }
  }
  for (long long i = 0; i < n; i++) {
    for (long long j = 0; j < 26; j++) {
      if (RangeQuery(0, 0, n - 1, i, i, j) > 0) {
        cout << char(j + 'a');
        break;
      }
    }
  }
}

### Prompt

Your task is to create a cpp solution to the following 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>

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
long long segTree[26][400005];
long long arr[100005];
long long lazy[26][400005];
long long n, m, t, l, r, x;
void Build(long long pos, long long low, long long high, long long bit) {
  if (low == high) {
    segTree[bit][pos] = (arr[low] == bit ? 1 : 0);
    return;
  }
  long long mid = (low + high) / 2;
  Build(2 * pos + 1, low, mid, bit);
  Build(2 * pos + 2, mid + 1, high, bit);
  segTree[bit][pos] = (segTree[bit][2 * pos + 1] + segTree[bit][2 * pos + 2]);
}
long long RangeQuery(long long pos, long long low, long long high,
                     long long qlow, long long qhigh, long long bit) {
  if (low > high) return 0;
  if (lazy[bit][pos] != -1) {
    if (low != high) {
      lazy[bit][2 * pos + 1] = lazy[bit][pos];
      lazy[bit][2 * pos + 2] = lazy[bit][pos];
    }
    segTree[bit][pos] = lazy[bit][pos] * (high - low + 1);
    lazy[bit][pos] = -1;
  }
  if (qlow <= low && qhigh >= high) return segTree[bit][pos];
  if (qlow > high || qhigh < low) return 0;
  long long mid = (low + high) / 2;
  long long a = RangeQuery(2 * pos + 1, low, mid, qlow, qhigh, bit);
  long long b = RangeQuery(2 * pos + 2, mid + 1, high, qlow, qhigh, bit);
  return (a + b);
}
void update(long long pos, long long low, long long high, long long ulow,
            long long uhigh, long long ch, long long ff) {
  if (low > high) return;
  if (lazy[ch][pos] != -1) {
    segTree[ch][pos] = lazy[ch][pos] * (high - low + 1);
    if (low != high) {
      lazy[ch][2 * pos + 1] = lazy[ch][pos];
      lazy[ch][2 * pos + 2] = lazy[ch][pos];
    }
    lazy[ch][pos] = -1;
  }
  if (ulow > high || uhigh < low) return;
  if (ulow <= low && uhigh >= high) {
    if (low != high) {
      lazy[ch][2 * pos + 1] = ff;
      lazy[ch][2 * pos + 2] = ff;
      segTree[ch][pos] = ff * (high - low + 1);
    } else
      segTree[ch][pos] = ff;
    lazy[ch][pos] = -1;
    return;
  }
  long long mid = (low + high) / 2;
  update(2 * pos + 1, low, mid, ulow, uhigh, ch, ff);
  update(2 * pos + 2, mid + 1, high, ulow, uhigh, ch, ff);
  segTree[ch][pos] = segTree[ch][2 * pos + 1] + segTree[ch][2 * pos + 2];
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  memset(lazy, -1, sizeof(lazy));
  cin >> n >> m;
  string str;
  cin >> str;
  for (long long i = 0; i < n; i++) arr[i] = (str[i] - 'a');
  for (long long i = 0; i < 26; i++) Build(0, 0, n - 1, i);
  while (m--) {
    cin >> l >> r >> t;
    l--;
    r--;
    long long freq[26];
    memset(freq, 0, sizeof(freq));
    for (long long i = 0; i < 26; i++)
      freq[i] = RangeQuery(0, 0, n - 1, l, r, i);
    if (t == 0) {
      long long st = l;
      for (long long i = 25; i >= 0; i--) {
        if (freq[i]) {
          update(0, 0, n - 1, l, r, i, 0);
          update(0, 0, n - 1, st, st + freq[i] - 1, i, 1);
          st = st + freq[i];
        }
      }
    } else {
      long long st = l;
      for (long long i = 0; i < 26; i++) {
        if (freq[i]) {
          update(0, 0, n - 1, l, r, i, 0);
          update(0, 0, n - 1, st, st + freq[i] - 1, i, 1);
          st = st + freq[i];
        }
      }
    }
  }
  for (long long i = 0; i < n; i++) {
    for (long long j = 0; j < 26; j++) {
      if (RangeQuery(0, 0, n - 1, i, i, j) > 0) {
        cout << char(j + 'a');
        break;
      }
    }
  }
}

```