#include <bits/stdc++.h>
using namespace std;
long long BigMod(long long B, long long P, long long M) {
  long long R = 1;
  while (P > 0) {
    if (P % 2 == 1) {
      R = (R * B) % M;
    }
    P /= 2;
    B = (B * B) % M;
  }
  return R;
}
template <class T1>
void deb(T1 e1) {
  cout << e1 << endl;
}
template <class T1, class T2>
void deb(T1 e1, T2 e2) {
  cout << e1 << " " << e2 << endl;
}
template <class T1, class T2, class T3>
void deb(T1 e1, T2 e2, T3 e3) {
  cout << e1 << " " << e2 << " " << e3 << endl;
}
template <class T1, class T2, class T3, class T4>
void deb(T1 e1, T2 e2, T3 e3, T4 e4) {
  cout << e1 << " " << e2 << " " << e3 << " " << e4 << endl;
}
template <class T1, class T2, class T3, class T4, class T5>
void deb(T1 e1, T2 e2, T3 e3, T4 e4, T5 e5) {
  cout << e1 << " " << e2 << " " << e3 << " " << e4 << " " << e5 << endl;
}
template <class T1, class T2, class T3, class T4, class T5, class T6>
void deb(T1 e1, T2 e2, T3 e3, T4 e4, T5 e5, T6 e6) {
  cout << e1 << " " << e2 << " " << e3 << " " << e4 << " " << e5 << " " << e6
       << endl;
}
const int MAX = 282144;
int tree[26][MAX];
bool lazy[26][MAX];
bool islazy[26][MAX];
void relax(int id, int idx, int l, int r, int val) {
  int nidx = (idx << 1);
  tree[id][idx] = (r - l + 1) * val;
  if (l != r) {
    lazy[id][nidx] = val;
    lazy[id][nidx | 1] = val;
    islazy[id][nidx] = true;
    islazy[id][nidx | 1] = true;
  }
  lazy[id][idx] = islazy[id][idx] = false;
  return;
}
int update(int id, int idx, int l, int r, int ql, int qr, int val) {
  if (l > r || ql > qr) return 0;
  if (islazy[id][idx]) {
    relax(id, idx, l, r, lazy[id][idx]);
  }
  if (l >= ql && r <= qr) {
    relax(id, idx, l, r, val);
    return tree[id][idx];
  }
  if (l > qr || r < ql) return tree[id][idx];
  int mid = (l + r) >> 1, nidx = (idx << 1);
  tree[id][idx] = update(id, nidx, l, mid, ql, qr, val) +
                  update(id, nidx | 1, mid + 1, r, ql, qr, val);
  return tree[id][idx];
}
int query(int id, int idx, int l, int r, int ql, int qr) {
  if (l > r || ql > qr) return 0;
  if (islazy[id][idx]) {
    relax(id, idx, l, r, lazy[id][idx]);
  }
  if (l >= ql && r <= qr) {
    return tree[id][idx];
  }
  if (l > qr || r < ql) return 0;
  int mid = (l + r) >> 1, nidx = (idx << 1);
  return query(id, nidx, l, mid, ql, qr) +
         query(id, nidx | 1, mid + 1, r, ql, qr);
}
char str[MAX];
int num[MAX];
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  scanf("%s", str);
  for (int i = 0; i < n; i++) {
    num[i] = str[i] - 'a';
  }
  for (int i = 0; i < n; i++) {
    update(num[i], 1, 0, n - 1, i, i, 1);
  }
  int l, r, k;
  for (int i = 0; i < m; i++) {
    scanf("%d %d %d", &l, &r, &k);
    l--;
    r--;
    if (k) {
      int in = 0, sum;
      for (int j = 0; j < 26; j++) {
        sum = query(j, 1, 0, n - 1, l, r);
        update(j, 1, 0, n - 1, l, r, 0);
        update(j, 1, 0, n - 1, l + in, l + in + sum - 1, 1);
        in += sum;
      }
    } else {
      int in = 0, sum;
      for (int j = 25; j > -1; j--) {
        sum = query(j, 1, 0, n - 1, l, r);
        update(j, 1, 0, n - 1, l, r, 0);
        update(j, 1, 0, n - 1, l + in, l + in + sum - 1, 1);
        in += sum;
      }
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 26; j++) {
      if (query(j, 1, 0, n - 1, i, i)) {
        str[i] = j + 'a';
        break;
      }
    }
  }
  printf("%s\n", str);
  return 0;
}

### Prompt

In cpp, your task is to solve 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;
long long BigMod(long long B, long long P, long long M) {
  long long R = 1;
  while (P > 0) {
    if (P % 2 == 1) {
      R = (R * B) % M;
    }
    P /= 2;
    B = (B * B) % M;
  }
  return R;
}
template <class T1>
void deb(T1 e1) {
  cout << e1 << endl;
}
template <class T1, class T2>
void deb(T1 e1, T2 e2) {
  cout << e1 << " " << e2 << endl;
}
template <class T1, class T2, class T3>
void deb(T1 e1, T2 e2, T3 e3) {
  cout << e1 << " " << e2 << " " << e3 << endl;
}
template <class T1, class T2, class T3, class T4>
void deb(T1 e1, T2 e2, T3 e3, T4 e4) {
  cout << e1 << " " << e2 << " " << e3 << " " << e4 << endl;
}
template <class T1, class T2, class T3, class T4, class T5>
void deb(T1 e1, T2 e2, T3 e3, T4 e4, T5 e5) {
  cout << e1 << " " << e2 << " " << e3 << " " << e4 << " " << e5 << endl;
}
template <class T1, class T2, class T3, class T4, class T5, class T6>
void deb(T1 e1, T2 e2, T3 e3, T4 e4, T5 e5, T6 e6) {
  cout << e1 << " " << e2 << " " << e3 << " " << e4 << " " << e5 << " " << e6
       << endl;
}
const int MAX = 282144;
int tree[26][MAX];
bool lazy[26][MAX];
bool islazy[26][MAX];
void relax(int id, int idx, int l, int r, int val) {
  int nidx = (idx << 1);
  tree[id][idx] = (r - l + 1) * val;
  if (l != r) {
    lazy[id][nidx] = val;
    lazy[id][nidx | 1] = val;
    islazy[id][nidx] = true;
    islazy[id][nidx | 1] = true;
  }
  lazy[id][idx] = islazy[id][idx] = false;
  return;
}
int update(int id, int idx, int l, int r, int ql, int qr, int val) {
  if (l > r || ql > qr) return 0;
  if (islazy[id][idx]) {
    relax(id, idx, l, r, lazy[id][idx]);
  }
  if (l >= ql && r <= qr) {
    relax(id, idx, l, r, val);
    return tree[id][idx];
  }
  if (l > qr || r < ql) return tree[id][idx];
  int mid = (l + r) >> 1, nidx = (idx << 1);
  tree[id][idx] = update(id, nidx, l, mid, ql, qr, val) +
                  update(id, nidx | 1, mid + 1, r, ql, qr, val);
  return tree[id][idx];
}
int query(int id, int idx, int l, int r, int ql, int qr) {
  if (l > r || ql > qr) return 0;
  if (islazy[id][idx]) {
    relax(id, idx, l, r, lazy[id][idx]);
  }
  if (l >= ql && r <= qr) {
    return tree[id][idx];
  }
  if (l > qr || r < ql) return 0;
  int mid = (l + r) >> 1, nidx = (idx << 1);
  return query(id, nidx, l, mid, ql, qr) +
         query(id, nidx | 1, mid + 1, r, ql, qr);
}
char str[MAX];
int num[MAX];
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  scanf("%s", str);
  for (int i = 0; i < n; i++) {
    num[i] = str[i] - 'a';
  }
  for (int i = 0; i < n; i++) {
    update(num[i], 1, 0, n - 1, i, i, 1);
  }
  int l, r, k;
  for (int i = 0; i < m; i++) {
    scanf("%d %d %d", &l, &r, &k);
    l--;
    r--;
    if (k) {
      int in = 0, sum;
      for (int j = 0; j < 26; j++) {
        sum = query(j, 1, 0, n - 1, l, r);
        update(j, 1, 0, n - 1, l, r, 0);
        update(j, 1, 0, n - 1, l + in, l + in + sum - 1, 1);
        in += sum;
      }
    } else {
      int in = 0, sum;
      for (int j = 25; j > -1; j--) {
        sum = query(j, 1, 0, n - 1, l, r);
        update(j, 1, 0, n - 1, l, r, 0);
        update(j, 1, 0, n - 1, l + in, l + in + sum - 1, 1);
        in += sum;
      }
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 26; j++) {
      if (query(j, 1, 0, n - 1, i, i)) {
        str[i] = j + 'a';
        break;
      }
    }
  }
  printf("%s\n", str);
  return 0;
}

```