#include <bits/stdc++.h>
using namespace std;
string s;
const int MAX_SIZE = 1e5;
int st[4 * MAX_SIZE][30];
int mark[4 * MAX_SIZE][30];
void build(int index, int cl, int cr) {
  if (cl > cr) return;
  if (cl == cr) {
    st[index][s[cl] - 'a'] = 1;
    for (int i = 0; i < 30; i++) mark[index][i] = -1;
  } else {
    int mid = (cl + cr) >> 1;
    build(2 * index + 1, cl, mid);
    build(2 * index + 2, mid + 1, cr);
    for (int i = 0; i < 30; i++) {
      st[index][i] = st[2 * index + 1][i] + st[2 * index + 2][i];
      mark[index][i] = -1;
    }
  }
}
void push(int index, int i, int cl, int mid, int cr) {
  if (mark[index][i] >= 0) {
    mark[2 * index + 1][i] = mark[index][i];
    mark[2 * index + 2][i] = mark[index][i];
    st[2 * index + 1][i] = (mid - cl + 1) * mark[index][i];
    st[2 * index + 2][i] = (cr - mid) * mark[index][i];
    mark[index][i] = -1;
  }
}
void update(int index, int l, int r, int cl, int cr, int val, int i) {
  if (cl > cr || l > r) return;
  if (cl == l && cr == r) {
    st[index][i] = (cr - cl + 1) * val;
    mark[index][i] = val;
  } else {
    int mid = (cl + cr) >> 1;
    push(index, i, cl, mid, cr);
    if (r <= mid)
      update(2 * index + 1, l, r, cl, mid, val, i);
    else if (l > mid)
      update(2 * index + 2, l, r, mid + 1, cr, val, i);
    else {
      update(2 * index + 1, l, mid, cl, mid, val, i);
      update(2 * index + 2, mid + 1, r, mid + 1, cr, val, i);
    }
    st[index][i] = st[2 * index + 1][i] + st[2 * index + 2][i];
  }
}
int getValue(int index, int l, int r, int cl, int cr, int i) {
  if (cl > cr || l > r) return 0;
  if (cl == l && cr == r) return st[index][i];
  int mid = (cl + cr) >> 1;
  push(index, i, cl, mid, cr);
  if (r <= mid)
    return getValue(2 * index + 1, l, r, cl, mid, i);
  else if (l > mid)
    return getValue(2 * index + 2, l, r, mid + 1, cr, i);
  return getValue(2 * index + 1, l, mid, cl, mid, i) +
         getValue(2 * index + 2, mid + 1, r, mid + 1, cr, i);
}
int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  cin >> s;
  build(0, 0, s.size() - 1);
  for (int i = 0; i < q; i++) {
    int l, r, type;
    cin >> l >> r >> type;
    l--, r--;
    vector<int> cnt(30, 0);
    for (int j = 0; j < 30; j++) cnt[j] = getValue(0, l, r, 0, s.size() - 1, j);
    for (int j = 0; j < 30; j++) update(0, l, r, 0, s.size() - 1, 0, j);
    if (type == 1) {
      for (int j = 0; j < 30; j++)
        if (cnt[j] > 0) {
          update(0, l, l + cnt[j] - 1, 0, s.size() - 1, 1, j);
          l += cnt[j];
        }
    } else {
      for (int j = 29; j >= 0; j--)
        if (cnt[j] > 0) {
          update(0, l, l + cnt[j] - 1, 0, s.size() - 1, 1, j);
          l += cnt[j];
        }
    }
  }
  for (int i = 0; i < s.size(); i++)
    for (int j = 0; j < 30; j++)
      if (getValue(0, i, i, 0, s.size() - 1, j)) {
        cout << char('a' + j);
        break;
      }
  cout << endl;
  return 0;
}

### Prompt

Develop a solution in CPP 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;
string s;
const int MAX_SIZE = 1e5;
int st[4 * MAX_SIZE][30];
int mark[4 * MAX_SIZE][30];
void build(int index, int cl, int cr) {
  if (cl > cr) return;
  if (cl == cr) {
    st[index][s[cl] - 'a'] = 1;
    for (int i = 0; i < 30; i++) mark[index][i] = -1;
  } else {
    int mid = (cl + cr) >> 1;
    build(2 * index + 1, cl, mid);
    build(2 * index + 2, mid + 1, cr);
    for (int i = 0; i < 30; i++) {
      st[index][i] = st[2 * index + 1][i] + st[2 * index + 2][i];
      mark[index][i] = -1;
    }
  }
}
void push(int index, int i, int cl, int mid, int cr) {
  if (mark[index][i] >= 0) {
    mark[2 * index + 1][i] = mark[index][i];
    mark[2 * index + 2][i] = mark[index][i];
    st[2 * index + 1][i] = (mid - cl + 1) * mark[index][i];
    st[2 * index + 2][i] = (cr - mid) * mark[index][i];
    mark[index][i] = -1;
  }
}
void update(int index, int l, int r, int cl, int cr, int val, int i) {
  if (cl > cr || l > r) return;
  if (cl == l && cr == r) {
    st[index][i] = (cr - cl + 1) * val;
    mark[index][i] = val;
  } else {
    int mid = (cl + cr) >> 1;
    push(index, i, cl, mid, cr);
    if (r <= mid)
      update(2 * index + 1, l, r, cl, mid, val, i);
    else if (l > mid)
      update(2 * index + 2, l, r, mid + 1, cr, val, i);
    else {
      update(2 * index + 1, l, mid, cl, mid, val, i);
      update(2 * index + 2, mid + 1, r, mid + 1, cr, val, i);
    }
    st[index][i] = st[2 * index + 1][i] + st[2 * index + 2][i];
  }
}
int getValue(int index, int l, int r, int cl, int cr, int i) {
  if (cl > cr || l > r) return 0;
  if (cl == l && cr == r) return st[index][i];
  int mid = (cl + cr) >> 1;
  push(index, i, cl, mid, cr);
  if (r <= mid)
    return getValue(2 * index + 1, l, r, cl, mid, i);
  else if (l > mid)
    return getValue(2 * index + 2, l, r, mid + 1, cr, i);
  return getValue(2 * index + 1, l, mid, cl, mid, i) +
         getValue(2 * index + 2, mid + 1, r, mid + 1, cr, i);
}
int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  cin >> s;
  build(0, 0, s.size() - 1);
  for (int i = 0; i < q; i++) {
    int l, r, type;
    cin >> l >> r >> type;
    l--, r--;
    vector<int> cnt(30, 0);
    for (int j = 0; j < 30; j++) cnt[j] = getValue(0, l, r, 0, s.size() - 1, j);
    for (int j = 0; j < 30; j++) update(0, l, r, 0, s.size() - 1, 0, j);
    if (type == 1) {
      for (int j = 0; j < 30; j++)
        if (cnt[j] > 0) {
          update(0, l, l + cnt[j] - 1, 0, s.size() - 1, 1, j);
          l += cnt[j];
        }
    } else {
      for (int j = 29; j >= 0; j--)
        if (cnt[j] > 0) {
          update(0, l, l + cnt[j] - 1, 0, s.size() - 1, 1, j);
          l += cnt[j];
        }
    }
  }
  for (int i = 0; i < s.size(); i++)
    for (int j = 0; j < 30; j++)
      if (getValue(0, i, i, 0, s.size() - 1, j)) {
        cout << char('a' + j);
        break;
      }
  cout << endl;
  return 0;
}

```