#include <bits/stdc++.h>
using namespace std;
const int MXN = 1e5 + 10;
int seg[26][265000][3];
int n, sz, q, sm;
void sum(int l, int r, int y, int x, int lx, int rx) {
  if (lx >= l && rx <= r) {
    sm += seg[y][x][0];
    seg[y][x][0] = 0;
    seg[y][x][1] = 1;
  } else if (lx < r && rx > l) {
    int mid = (lx + rx) / 2;
    if (seg[y][x][1]) {
      seg[y][2 * x + 1][1] = seg[y][x][1];
      seg[y][2 * x + 1][0] = (seg[y][2 * x + 1][1] - 1) * seg[y][2 * x + 1][2];
      seg[y][2 * x + 2][1] = seg[y][x][1];
      seg[y][2 * x + 2][0] = (seg[y][2 * x + 2][1] - 1) * seg[y][2 * x + 2][2];
      seg[y][x][1] = 0;
    }
    sum(l, r, y, 2 * x + 1, lx, mid);
    sum(l, r, y, 2 * x + 2, mid, rx);
    seg[y][x][0] = seg[y][2 * x + 1][0] + seg[y][2 * x + 2][0];
  }
}
void add(int l, int r, int y, int x, int lx, int rx) {
  if (lx >= l && rx <= r) {
    seg[y][x][0] = seg[y][x][2];
    seg[y][x][1] = 2;
  } else if (lx < r && rx > l) {
    if (seg[y][x][1]) {
      seg[y][2 * x + 1][1] = seg[y][x][1];
      seg[y][2 * x + 1][0] = (seg[y][2 * x + 1][1] - 1) * seg[y][2 * x + 1][2];
      seg[y][2 * x + 2][1] = seg[y][x][1];
      seg[y][2 * x + 2][0] = (seg[y][2 * x + 2][1] - 1) * seg[y][2 * x + 2][2];
      seg[y][x][1] = 0;
    }
    int mid = (lx + rx) / 2;
    add(l, r, y, 2 * x + 1, lx, mid);
    add(l, r, y, 2 * x + 2, mid, rx);
    seg[y][x][0] = seg[y][2 * x + 1][0] + seg[y][2 * x + 2][0];
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  string s;
  cin >> n >> q >> s;
  sz = 1;
  while (sz < n) sz *= 2;
  for (int i = 0; i < n; i++) seg[int(s[i]) - 97][sz + i - 1][0] = 1;
  for (int i = sz - 1; i < sz + n - 1; i++) {
    for (int j = 0; j < 26; j++) seg[j][i][2] = 1;
  }
  for (int i = sz - 2; i >= 0; i--) {
    for (int j = 0; j < 26; j++) {
      seg[j][i][0] = seg[j][2 * i + 1][0] + seg[j][2 * i + 2][0];
      seg[j][i][2] = seg[j][2 * i + 1][2] + seg[j][2 * i + 2][2];
    }
  }
  while (q--) {
    int l, r;
    bool a;
    cin >> l >> r >> a;
    l--;
    int b = l;
    if (a == 0) {
      b = r;
      for (int i = 0; i < 26 && b >= l; i++) {
        sm = 0;
        sum(l, r, i, 0, 0, sz);
        add(b - sm, b, i, 0, 0, sz);
        b -= sm;
      }
    } else {
      for (int i = 0; i < 26 && b < r; i++) {
        sm = 0;
        sum(l, r, i, 0, 0, sz);
        add(b, b + sm, i, 0, 0, sz);
        b += sm;
      }
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 26; j++) {
      sm = 0;
      sum(i, i + 1, j, 0, 0, sz);
      if (sm) {
        cout << char('a' + j);
        break;
      }
    }
  }
}

### Prompt

Please formulate 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;
const int MXN = 1e5 + 10;
int seg[26][265000][3];
int n, sz, q, sm;
void sum(int l, int r, int y, int x, int lx, int rx) {
  if (lx >= l && rx <= r) {
    sm += seg[y][x][0];
    seg[y][x][0] = 0;
    seg[y][x][1] = 1;
  } else if (lx < r && rx > l) {
    int mid = (lx + rx) / 2;
    if (seg[y][x][1]) {
      seg[y][2 * x + 1][1] = seg[y][x][1];
      seg[y][2 * x + 1][0] = (seg[y][2 * x + 1][1] - 1) * seg[y][2 * x + 1][2];
      seg[y][2 * x + 2][1] = seg[y][x][1];
      seg[y][2 * x + 2][0] = (seg[y][2 * x + 2][1] - 1) * seg[y][2 * x + 2][2];
      seg[y][x][1] = 0;
    }
    sum(l, r, y, 2 * x + 1, lx, mid);
    sum(l, r, y, 2 * x + 2, mid, rx);
    seg[y][x][0] = seg[y][2 * x + 1][0] + seg[y][2 * x + 2][0];
  }
}
void add(int l, int r, int y, int x, int lx, int rx) {
  if (lx >= l && rx <= r) {
    seg[y][x][0] = seg[y][x][2];
    seg[y][x][1] = 2;
  } else if (lx < r && rx > l) {
    if (seg[y][x][1]) {
      seg[y][2 * x + 1][1] = seg[y][x][1];
      seg[y][2 * x + 1][0] = (seg[y][2 * x + 1][1] - 1) * seg[y][2 * x + 1][2];
      seg[y][2 * x + 2][1] = seg[y][x][1];
      seg[y][2 * x + 2][0] = (seg[y][2 * x + 2][1] - 1) * seg[y][2 * x + 2][2];
      seg[y][x][1] = 0;
    }
    int mid = (lx + rx) / 2;
    add(l, r, y, 2 * x + 1, lx, mid);
    add(l, r, y, 2 * x + 2, mid, rx);
    seg[y][x][0] = seg[y][2 * x + 1][0] + seg[y][2 * x + 2][0];
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  string s;
  cin >> n >> q >> s;
  sz = 1;
  while (sz < n) sz *= 2;
  for (int i = 0; i < n; i++) seg[int(s[i]) - 97][sz + i - 1][0] = 1;
  for (int i = sz - 1; i < sz + n - 1; i++) {
    for (int j = 0; j < 26; j++) seg[j][i][2] = 1;
  }
  for (int i = sz - 2; i >= 0; i--) {
    for (int j = 0; j < 26; j++) {
      seg[j][i][0] = seg[j][2 * i + 1][0] + seg[j][2 * i + 2][0];
      seg[j][i][2] = seg[j][2 * i + 1][2] + seg[j][2 * i + 2][2];
    }
  }
  while (q--) {
    int l, r;
    bool a;
    cin >> l >> r >> a;
    l--;
    int b = l;
    if (a == 0) {
      b = r;
      for (int i = 0; i < 26 && b >= l; i++) {
        sm = 0;
        sum(l, r, i, 0, 0, sz);
        add(b - sm, b, i, 0, 0, sz);
        b -= sm;
      }
    } else {
      for (int i = 0; i < 26 && b < r; i++) {
        sm = 0;
        sum(l, r, i, 0, 0, sz);
        add(b, b + sm, i, 0, 0, sz);
        b += sm;
      }
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 26; j++) {
      sm = 0;
      sum(i, i + 1, j, 0, 0, sz);
      if (sm) {
        cout << char('a' + j);
        break;
      }
    }
  }
}

```