#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC target("sse4")
const long double PI = 3.14159265358979323;
long long int linf = (long long int)2e18;
const int inf = 1011111111;
const int N = 100005;
int n, q;
int sgt[26][4 * N], lazy[26][4 * N];
string str;
void input() { cin >> n >> q >> str; }
void propogate(int idx, int start, int end, int id) {
  sgt[id][idx] = (end - start + 1) * (lazy[id][idx]);
  if (start != end) {
    lazy[id][2 * idx + 1] = lazy[id][idx];
    lazy[id][2 * idx + 2] = lazy[id][idx];
  }
  lazy[id][idx] = -1;
  return;
}
void build(int idx, int start, int end, int id) {
  if (start == end) {
    if ((int)(str[start] - 'a') == id) sgt[id][idx] = 1;
    return;
  }
  int mid = (start + end) / 2;
  build(2 * idx + 1, start, mid, id);
  build(2 * idx + 2, mid + 1, end, id);
  sgt[id][idx] = sgt[id][2 * idx + 1] + sgt[id][2 * idx + 2];
  return;
}
int query(int idx, int start, int end, int l, int r, int id) {
  if (lazy[id][idx] != -1) {
    propogate(idx, start, end, id);
  }
  if (l > end or r < start) return 0;
  if (start >= l and end <= r) return sgt[id][idx];
  int mid = (start + end) / 2;
  int q1 = query(2 * idx + 1, start, mid, l, r, id);
  int q2 = query(2 * idx + 2, mid + 1, end, l, r, id);
  return q1 + q2;
}
void update(int idx, int start, int end, int id, int l, int r, int val) {
  if (lazy[id][idx] != -1) propogate(idx, start, end, id);
  if (l > r) return;
  if (l > end or r < start) return;
  if (start >= l and end <= r) {
    lazy[id][idx] = val;
    propogate(idx, start, end, id);
    return;
  }
  int mid = (start + end) / 2;
  update(2 * idx + 1, start, mid, id, l, r, val);
  update(2 * idx + 2, mid + 1, end, id, l, r, val);
  sgt[id][idx] = sgt[id][2 * idx + 1] + sgt[id][2 * idx + 2];
  return;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int test = 1;
  while (test--) {
    input();
    for (int i = 0; i < 4 * N; i++) {
      for (int j = 0; j < 26; j++) lazy[j][i] = -1;
    }
    for (int i = 0; i < 26; i++) {
      build(0, 0, n - 1, i);
    }
    while (q--) {
      int l, r, k;
      cin >> l >> r >> k;
      l--;
      r--;
      vector<int> v1(26);
      int sum = 0;
      for (int i = 0; i < 26; i++) {
        v1[i] = query(0, 0, n - 1, l, r, i);
        sum += v1[i];
      }
      if (k == 1) {
        int sum = 0;
        for (int i = 0; i < 26; i++) {
          if (v1[i] == 0) continue;
          update(0, 0, n - 1, i, l + sum, l + sum + v1[i] - 1, 1);
          update(0, 0, n - 1, i, l, l + sum - 1, 0);
          update(0, 0, n - 1, i, l + sum + v1[i], r, 0);
          sum += v1[i];
        }
      } else {
        int sum = 0;
        for (int i = 25; i >= 0; i--) {
          if (v1[i] == 0) continue;
          update(0, 0, n - 1, i, l + sum, l + sum + v1[i] - 1, 1);
          update(0, 0, n - 1, i, l, l + sum - 1, 0);
          update(0, 0, n - 1, i, l + sum + v1[i], r, 0);
          sum += v1[i];
        }
      }
    }
    string ans = "";
    for (int i = 0; i < n; i++) {
      for (int j = 0; j <= 25; j++) {
        if (query(0, 0, n - 1, i, i, j)) {
          ans += (char)(97 + j);
          break;
        }
      }
    }
    cout << ans << "\n";
  }
  cerr << '\n'
       << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
  return 0;
}

### Prompt

Please provide a cpp coded solution to the problem described below:

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;
#pragma GCC optimize("O3")
#pragma GCC target("sse4")
const long double PI = 3.14159265358979323;
long long int linf = (long long int)2e18;
const int inf = 1011111111;
const int N = 100005;
int n, q;
int sgt[26][4 * N], lazy[26][4 * N];
string str;
void input() { cin >> n >> q >> str; }
void propogate(int idx, int start, int end, int id) {
  sgt[id][idx] = (end - start + 1) * (lazy[id][idx]);
  if (start != end) {
    lazy[id][2 * idx + 1] = lazy[id][idx];
    lazy[id][2 * idx + 2] = lazy[id][idx];
  }
  lazy[id][idx] = -1;
  return;
}
void build(int idx, int start, int end, int id) {
  if (start == end) {
    if ((int)(str[start] - 'a') == id) sgt[id][idx] = 1;
    return;
  }
  int mid = (start + end) / 2;
  build(2 * idx + 1, start, mid, id);
  build(2 * idx + 2, mid + 1, end, id);
  sgt[id][idx] = sgt[id][2 * idx + 1] + sgt[id][2 * idx + 2];
  return;
}
int query(int idx, int start, int end, int l, int r, int id) {
  if (lazy[id][idx] != -1) {
    propogate(idx, start, end, id);
  }
  if (l > end or r < start) return 0;
  if (start >= l and end <= r) return sgt[id][idx];
  int mid = (start + end) / 2;
  int q1 = query(2 * idx + 1, start, mid, l, r, id);
  int q2 = query(2 * idx + 2, mid + 1, end, l, r, id);
  return q1 + q2;
}
void update(int idx, int start, int end, int id, int l, int r, int val) {
  if (lazy[id][idx] != -1) propogate(idx, start, end, id);
  if (l > r) return;
  if (l > end or r < start) return;
  if (start >= l and end <= r) {
    lazy[id][idx] = val;
    propogate(idx, start, end, id);
    return;
  }
  int mid = (start + end) / 2;
  update(2 * idx + 1, start, mid, id, l, r, val);
  update(2 * idx + 2, mid + 1, end, id, l, r, val);
  sgt[id][idx] = sgt[id][2 * idx + 1] + sgt[id][2 * idx + 2];
  return;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int test = 1;
  while (test--) {
    input();
    for (int i = 0; i < 4 * N; i++) {
      for (int j = 0; j < 26; j++) lazy[j][i] = -1;
    }
    for (int i = 0; i < 26; i++) {
      build(0, 0, n - 1, i);
    }
    while (q--) {
      int l, r, k;
      cin >> l >> r >> k;
      l--;
      r--;
      vector<int> v1(26);
      int sum = 0;
      for (int i = 0; i < 26; i++) {
        v1[i] = query(0, 0, n - 1, l, r, i);
        sum += v1[i];
      }
      if (k == 1) {
        int sum = 0;
        for (int i = 0; i < 26; i++) {
          if (v1[i] == 0) continue;
          update(0, 0, n - 1, i, l + sum, l + sum + v1[i] - 1, 1);
          update(0, 0, n - 1, i, l, l + sum - 1, 0);
          update(0, 0, n - 1, i, l + sum + v1[i], r, 0);
          sum += v1[i];
        }
      } else {
        int sum = 0;
        for (int i = 25; i >= 0; i--) {
          if (v1[i] == 0) continue;
          update(0, 0, n - 1, i, l + sum, l + sum + v1[i] - 1, 1);
          update(0, 0, n - 1, i, l, l + sum - 1, 0);
          update(0, 0, n - 1, i, l + sum + v1[i], r, 0);
          sum += v1[i];
        }
      }
    }
    string ans = "";
    for (int i = 0; i < n; i++) {
      for (int j = 0; j <= 25; j++) {
        if (query(0, 0, n - 1, i, i, j)) {
          ans += (char)(97 + j);
          break;
        }
      }
    }
    cout << ans << "\n";
  }
  cerr << '\n'
       << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
  return 0;
}

```