#include <bits/stdc++.h>
using namespace std;
int const N = 102000;
int len, seg[4 * N][26];
bool lazy[4 * N];
char s[N];
void fix(int node, int start, int end) {
  if (start != end) {
    for (int i = 0; i < 26; i++) {
      seg[node * 2][i] = 0;
      seg[node * 2 + 1][i] = 0;
      if (seg[node][i] != 0) {
        int mid = (start + end) / 2;
        seg[node * 2][i] = mid - start + 1;
        seg[node * 2 + 1][i] = end - mid;
        lazy[node * 2 + 1] = 1;
        lazy[node * 2] = 1;
      }
    }
  }
  lazy[node] = false;
}
void build(int node, int start, int end) {
  if (start == end)
    seg[node][s[start - 1] - 'a'] = 1;
  else {
    int mid = (start + end) / 2;
    build(node * 2, start, mid);
    build(node * 2 + 1, mid + 1, end);
    for (int i = 0; i < 26; i++)
      seg[node][i] = seg[node * 2][i] + seg[node * 2 + 1][i];
  }
}
int l, r;
int get(int node, int start, int end, int ch) {
  if (lazy[node]) fix(node, start, end);
  if (start > r || end < l) return 0;
  if (start >= l && end <= r) return seg[node][ch];
  int mid = (start + end) / 2;
  return get(node * 2, start, mid, ch) + get(node * 2 + 1, mid + 1, end, ch);
}
int k;
void up(int node, int start, int end, int ch) {
  if (lazy[node]) fix(node, start, end);
  if (start > k || end < l) return;
  if (start >= l && end <= k) {
    for (int i = 0; i < 26; i++) seg[node][i] = 0;
    seg[node][ch] += end - start + 1;
    lazy[node] = 1;
    return;
  }
  int mid = (start + end) / 2;
  up(node * 2, start, mid, ch);
  up(node * 2 + 1, mid + 1, end, ch);
  for (int i = 0; i < 26; i++)
    seg[node][i] = seg[node * 2][i] + seg[node * 2 + 1][i];
}
void calc(int node, int start, int end) {
  if (lazy[node]) fix(node, start, end);
  if (start == end) {
    for (int i = 0; i < 26; i++)
      if (seg[node][i] != 0) {
        cout << char(i + 'a');
        return;
      }
  }
  int mid = (start + end) / 2;
  calc(node * 2, start, mid);
  calc(node * 2 + 1, mid + 1, end);
}
int main() {
  int q;
  scanf("%d%d%s", &len, &q, s);
  build(1, 1, len);
  while (q--) {
    int t;
    scanf("%d%d%d", &l, &r, &t);
    int frq[26];
    k = l;
    for (int i = 0; i < 26; i++) frq[i] = get(1, 1, len, i);
    if (t == 1) {
      for (int i = 0; i < 26; i++) {
        if (frq[i]) {
          k += frq[i] - 1;
          up(1, 1, len, i);
          k++;
          l = k;
        }
      }
    } else
      for (int i = 25; i >= 0; i--) {
        if (frq[i]) {
          k += frq[i] - 1;
          up(1, 1, len, i);
          k++;
          l = k;
        }
      }
  }
  calc(1, 1, len);
  return 0;
}

### Prompt

Your challenge is to write 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;
int const N = 102000;
int len, seg[4 * N][26];
bool lazy[4 * N];
char s[N];
void fix(int node, int start, int end) {
  if (start != end) {
    for (int i = 0; i < 26; i++) {
      seg[node * 2][i] = 0;
      seg[node * 2 + 1][i] = 0;
      if (seg[node][i] != 0) {
        int mid = (start + end) / 2;
        seg[node * 2][i] = mid - start + 1;
        seg[node * 2 + 1][i] = end - mid;
        lazy[node * 2 + 1] = 1;
        lazy[node * 2] = 1;
      }
    }
  }
  lazy[node] = false;
}
void build(int node, int start, int end) {
  if (start == end)
    seg[node][s[start - 1] - 'a'] = 1;
  else {
    int mid = (start + end) / 2;
    build(node * 2, start, mid);
    build(node * 2 + 1, mid + 1, end);
    for (int i = 0; i < 26; i++)
      seg[node][i] = seg[node * 2][i] + seg[node * 2 + 1][i];
  }
}
int l, r;
int get(int node, int start, int end, int ch) {
  if (lazy[node]) fix(node, start, end);
  if (start > r || end < l) return 0;
  if (start >= l && end <= r) return seg[node][ch];
  int mid = (start + end) / 2;
  return get(node * 2, start, mid, ch) + get(node * 2 + 1, mid + 1, end, ch);
}
int k;
void up(int node, int start, int end, int ch) {
  if (lazy[node]) fix(node, start, end);
  if (start > k || end < l) return;
  if (start >= l && end <= k) {
    for (int i = 0; i < 26; i++) seg[node][i] = 0;
    seg[node][ch] += end - start + 1;
    lazy[node] = 1;
    return;
  }
  int mid = (start + end) / 2;
  up(node * 2, start, mid, ch);
  up(node * 2 + 1, mid + 1, end, ch);
  for (int i = 0; i < 26; i++)
    seg[node][i] = seg[node * 2][i] + seg[node * 2 + 1][i];
}
void calc(int node, int start, int end) {
  if (lazy[node]) fix(node, start, end);
  if (start == end) {
    for (int i = 0; i < 26; i++)
      if (seg[node][i] != 0) {
        cout << char(i + 'a');
        return;
      }
  }
  int mid = (start + end) / 2;
  calc(node * 2, start, mid);
  calc(node * 2 + 1, mid + 1, end);
}
int main() {
  int q;
  scanf("%d%d%s", &len, &q, s);
  build(1, 1, len);
  while (q--) {
    int t;
    scanf("%d%d%d", &l, &r, &t);
    int frq[26];
    k = l;
    for (int i = 0; i < 26; i++) frq[i] = get(1, 1, len, i);
    if (t == 1) {
      for (int i = 0; i < 26; i++) {
        if (frq[i]) {
          k += frq[i] - 1;
          up(1, 1, len, i);
          k++;
          l = k;
        }
      }
    } else
      for (int i = 25; i >= 0; i--) {
        if (frq[i]) {
          k += frq[i] - 1;
          up(1, 1, len, i);
          k++;
          l = k;
        }
      }
  }
  calc(1, 1, len);
  return 0;
}

```