#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5, ALPHALEN = 26;
int q, n, segTree[ALPHALEN + 1][4 * MAXN + 1], lazy[ALPHALEN + 1][4 * MAXN + 1],
    cnt[ALPHALEN];
char s[MAXN + 1];
void readData() {
  cin >> n >> q;
  cin >> (s + 1);
}
void buildTree(int node, int left, int right) {
  if (left == right) {
    int ch = s[left] - 'a';
    segTree[ch][node] = 1;
    for (int i = 0; i < ALPHALEN; i++) lazy[i][node] = -1;
  } else {
    int m = (left + right) / 2;
    buildTree(2 * node, left, m);
    buildTree(2 * node + 1, m + 1, right);
    for (int i = 0; i < ALPHALEN; i++) {
      lazy[i][node] = -1;
      segTree[i][node] = segTree[i][2 * node + 1] + segTree[i][2 * node];
    }
  }
}
void updateTree(int node, int left, int right, int a, int b, int ch,
                int state) {
  if (lazy[ch][node] != -1) {
    segTree[ch][node] = lazy[ch][node] * (right - left + 1);
    if (right != left) {
      lazy[ch][2 * node] = lazy[ch][node];
      lazy[ch][2 * node + 1] = lazy[ch][node];
    }
    lazy[ch][node] = -1;
  }
  if (right < a || left > b) return;
  if (a <= left && right <= b) {
    lazy[ch][node] = state;
    segTree[ch][node] = lazy[ch][node] * (right - left + 1);
    if (right != left) {
      lazy[ch][2 * node] = lazy[ch][node];
      lazy[ch][2 * node + 1] = lazy[ch][node];
    }
    lazy[ch][node] = -1;
    return;
  }
  int mid = (left + right) / 2;
  updateTree(2 * node, left, mid, a, b, ch, state);
  updateTree(2 * node + 1, mid + 1, right, a, b, ch, state);
  segTree[ch][node] = segTree[ch][2 * node] + segTree[ch][2 * node + 1];
}
int querry(int node, int left, int right, int a, int b, int ch) {
  if (right < a || left > b) return 0;
  if (lazy[ch][node] != -1) {
    segTree[ch][node] = lazy[ch][node] * (right - left + 1);
    if (right != left) {
      lazy[ch][2 * node] = lazy[ch][node];
      lazy[ch][2 * node + 1] = lazy[ch][node];
    }
    lazy[ch][node] = -1;
  }
  if (a <= left && right <= b) return segTree[ch][node];
  int mid = (left + right) / 2;
  return querry(2 * node, left, mid, a, b, ch) +
         querry(2 * node + 1, mid + 1, right, a, b, ch);
}
void get(int node, int left, int right, int a, int b, int ch) {
  if (lazy[ch][node] != -1) {
    segTree[ch][node] = lazy[ch][node] * (right - left + 1);
    if (right != left) {
      lazy[ch][2 * node] = lazy[ch][node];
      lazy[ch][2 * node + 1] = lazy[ch][node];
    }
    lazy[ch][node] = -1;
  }
  if (segTree[ch][node] == 0) return;
  if (right < a || left > b) return;
  if (left == right) {
    s[left] = 'a' + ch;
    return;
  }
  int mid = (left + right) / 2;
  get(2 * node, left, mid, a, b, ch);
  get(2 * node + 1, mid + 1, right, a, b, ch);
}
int main() {
  readData();
  buildTree(1, 1, n);
  for (int i = 1; i <= q; i++) {
    int x, y, k;
    cin >> x >> y >> k;
    for (int j = 0; j < ALPHALEN; j++) cnt[j] = querry(1, 1, n, x, y, j);
    int curr;
    if (k == 1)
      curr = x;
    else
      curr = y;
    for (int j = 0; j < ALPHALEN; j++) {
      if (cnt[j] != 0) {
        updateTree(1, 1, n, x, y, j, 0);
        if (k == 1) {
          updateTree(1, 1, n, curr, curr + cnt[j] - 1, j, 1);
          curr += cnt[j];
        } else {
          updateTree(1, 1, n, curr - cnt[j] + 1, curr, j, 1);
          curr -= cnt[j];
        }
      }
    }
  }
  for (int i = 0; i < ALPHALEN; i++) get(1, 1, n, 1, n, i);
  cout << (s + 1);
  return 0;
}

### Prompt

Create a solution in cpp for 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;
const int MAXN = 1e5, ALPHALEN = 26;
int q, n, segTree[ALPHALEN + 1][4 * MAXN + 1], lazy[ALPHALEN + 1][4 * MAXN + 1],
    cnt[ALPHALEN];
char s[MAXN + 1];
void readData() {
  cin >> n >> q;
  cin >> (s + 1);
}
void buildTree(int node, int left, int right) {
  if (left == right) {
    int ch = s[left] - 'a';
    segTree[ch][node] = 1;
    for (int i = 0; i < ALPHALEN; i++) lazy[i][node] = -1;
  } else {
    int m = (left + right) / 2;
    buildTree(2 * node, left, m);
    buildTree(2 * node + 1, m + 1, right);
    for (int i = 0; i < ALPHALEN; i++) {
      lazy[i][node] = -1;
      segTree[i][node] = segTree[i][2 * node + 1] + segTree[i][2 * node];
    }
  }
}
void updateTree(int node, int left, int right, int a, int b, int ch,
                int state) {
  if (lazy[ch][node] != -1) {
    segTree[ch][node] = lazy[ch][node] * (right - left + 1);
    if (right != left) {
      lazy[ch][2 * node] = lazy[ch][node];
      lazy[ch][2 * node + 1] = lazy[ch][node];
    }
    lazy[ch][node] = -1;
  }
  if (right < a || left > b) return;
  if (a <= left && right <= b) {
    lazy[ch][node] = state;
    segTree[ch][node] = lazy[ch][node] * (right - left + 1);
    if (right != left) {
      lazy[ch][2 * node] = lazy[ch][node];
      lazy[ch][2 * node + 1] = lazy[ch][node];
    }
    lazy[ch][node] = -1;
    return;
  }
  int mid = (left + right) / 2;
  updateTree(2 * node, left, mid, a, b, ch, state);
  updateTree(2 * node + 1, mid + 1, right, a, b, ch, state);
  segTree[ch][node] = segTree[ch][2 * node] + segTree[ch][2 * node + 1];
}
int querry(int node, int left, int right, int a, int b, int ch) {
  if (right < a || left > b) return 0;
  if (lazy[ch][node] != -1) {
    segTree[ch][node] = lazy[ch][node] * (right - left + 1);
    if (right != left) {
      lazy[ch][2 * node] = lazy[ch][node];
      lazy[ch][2 * node + 1] = lazy[ch][node];
    }
    lazy[ch][node] = -1;
  }
  if (a <= left && right <= b) return segTree[ch][node];
  int mid = (left + right) / 2;
  return querry(2 * node, left, mid, a, b, ch) +
         querry(2 * node + 1, mid + 1, right, a, b, ch);
}
void get(int node, int left, int right, int a, int b, int ch) {
  if (lazy[ch][node] != -1) {
    segTree[ch][node] = lazy[ch][node] * (right - left + 1);
    if (right != left) {
      lazy[ch][2 * node] = lazy[ch][node];
      lazy[ch][2 * node + 1] = lazy[ch][node];
    }
    lazy[ch][node] = -1;
  }
  if (segTree[ch][node] == 0) return;
  if (right < a || left > b) return;
  if (left == right) {
    s[left] = 'a' + ch;
    return;
  }
  int mid = (left + right) / 2;
  get(2 * node, left, mid, a, b, ch);
  get(2 * node + 1, mid + 1, right, a, b, ch);
}
int main() {
  readData();
  buildTree(1, 1, n);
  for (int i = 1; i <= q; i++) {
    int x, y, k;
    cin >> x >> y >> k;
    for (int j = 0; j < ALPHALEN; j++) cnt[j] = querry(1, 1, n, x, y, j);
    int curr;
    if (k == 1)
      curr = x;
    else
      curr = y;
    for (int j = 0; j < ALPHALEN; j++) {
      if (cnt[j] != 0) {
        updateTree(1, 1, n, x, y, j, 0);
        if (k == 1) {
          updateTree(1, 1, n, curr, curr + cnt[j] - 1, j, 1);
          curr += cnt[j];
        } else {
          updateTree(1, 1, n, curr - cnt[j] + 1, curr, j, 1);
          curr -= cnt[j];
        }
      }
    }
  }
  for (int i = 0; i < ALPHALEN; i++) get(1, 1, n, 1, n, i);
  cout << (s + 1);
  return 0;
}

```