#include <bits/stdc++.h>
const int N = 110000, CN = 30, C = 26;
int t[3 * N][CN], lazy[3 * N];
void clear(int *t) { memset(t, 0, C * sizeof(int)); }
void copy(int *t, const int *s) { memcpy(t, s, C * sizeof(int)); }
void add(int *t, const int *s) {
  for (int i = 0; i < C; i++) {
    t[i] += s[i];
  }
}
void pushDown(unsigned pos, int lv) {
  if (lazy[pos] >= 0) {
    clear(t[pos]);
    t[pos][lazy[pos]] = 1 << lv;
    if (lv > 0) {
      lazy[pos << 1] = lazy[pos];
      lazy[(pos << 1) | 1] = lazy[pos];
    }
    lazy[pos] = -1;
  }
}
void update(unsigned pos, int lv) {
  if (pos) {
    clear(t[pos]);
    pushDown(pos << 1, lv - 1);
    add(t[pos], t[pos << 1]);
    pushDown((pos << 1) | 1, lv - 1);
    add(t[pos], t[(pos << 1) | 1]);
  }
}
void fill(unsigned pos, unsigned l, unsigned r, int lv, int num) {
  if (((pos + 1) << lv) <= l || r <= (pos << lv)) {
    return;
  }
  if (l <= (pos << lv) && ((pos + 1) << lv) <= r) {
    lazy[pos] = num;
  } else {
    pushDown(pos, lv);
    fill(pos << 1, l, r, lv - 1, num);
    fill((pos << 1) | 1, l, r, lv - 1, num);
    update(pos, lv);
  }
}
void query(unsigned pos, unsigned l, unsigned r, int lv, int *res) {
  if (((pos + 1) << lv) <= l || r <= (pos << lv)) {
    return;
  }
  pushDown(pos, lv);
  if (l <= (pos << lv) && ((pos + 1) << lv) <= r) {
    add(res, t[pos]);
  } else {
    query(pos << 1, l, r, lv - 1, res);
    query((pos << 1) | 1, l, r, lv - 1, res);
  }
}
int main() {
  int n, q;
  scanf("%d%d", &n, &q);
  int lv = 0;
  while ((1 << lv) <= n) {
    lv++;
  }
  memset(t, 0, sizeof(t));
  memset(lazy, -1, sizeof(lazy));
  for (int i = 0; i < n; i++) {
    char ch;
    scanf(" %c", &ch);
    fill(1, (1 << lv) | i, (1 << lv) | (i + 1), lv, ch - 'a');
  }
  for (int i = 0; i < q; i++) {
    int l, r, op;
    scanf("%d%d%d", &l, &r, &op);
    l--;
    int got[CN];
    clear(got);
    query(1, (1 << lv) | l, (1 << lv) | r, lv, got);
    if (op == 1) {
      int begin = l;
      for (int ch = 0; ch < C; ch++) {
        fill(1, (1 << lv) | begin, (1 << lv) | (begin + got[ch]), lv, ch);
        begin += got[ch];
      }
    } else if (op == 0) {
      int begin = r;
      for (int ch = 0; ch < C; ch++) {
        fill(1, (1 << lv) | (begin - got[ch]), (1 << lv) | begin, lv, ch);
        begin -= got[ch];
      }
    }
  }
  for (int i = 0; i < n; i++) {
    int got[CN];
    clear(got);
    query(1, (1 << lv) | i, (1 << lv) | (i + 1), lv, got);
    for (int ch = 0; ch < C; ch++) {
      if (got[ch]) {
        putchar('a' + ch);
        break;
      }
    }
  }
  putchar('\n');
  return 0;
}

### Prompt

Please provide a Cpp coded solution 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>
const int N = 110000, CN = 30, C = 26;
int t[3 * N][CN], lazy[3 * N];
void clear(int *t) { memset(t, 0, C * sizeof(int)); }
void copy(int *t, const int *s) { memcpy(t, s, C * sizeof(int)); }
void add(int *t, const int *s) {
  for (int i = 0; i < C; i++) {
    t[i] += s[i];
  }
}
void pushDown(unsigned pos, int lv) {
  if (lazy[pos] >= 0) {
    clear(t[pos]);
    t[pos][lazy[pos]] = 1 << lv;
    if (lv > 0) {
      lazy[pos << 1] = lazy[pos];
      lazy[(pos << 1) | 1] = lazy[pos];
    }
    lazy[pos] = -1;
  }
}
void update(unsigned pos, int lv) {
  if (pos) {
    clear(t[pos]);
    pushDown(pos << 1, lv - 1);
    add(t[pos], t[pos << 1]);
    pushDown((pos << 1) | 1, lv - 1);
    add(t[pos], t[(pos << 1) | 1]);
  }
}
void fill(unsigned pos, unsigned l, unsigned r, int lv, int num) {
  if (((pos + 1) << lv) <= l || r <= (pos << lv)) {
    return;
  }
  if (l <= (pos << lv) && ((pos + 1) << lv) <= r) {
    lazy[pos] = num;
  } else {
    pushDown(pos, lv);
    fill(pos << 1, l, r, lv - 1, num);
    fill((pos << 1) | 1, l, r, lv - 1, num);
    update(pos, lv);
  }
}
void query(unsigned pos, unsigned l, unsigned r, int lv, int *res) {
  if (((pos + 1) << lv) <= l || r <= (pos << lv)) {
    return;
  }
  pushDown(pos, lv);
  if (l <= (pos << lv) && ((pos + 1) << lv) <= r) {
    add(res, t[pos]);
  } else {
    query(pos << 1, l, r, lv - 1, res);
    query((pos << 1) | 1, l, r, lv - 1, res);
  }
}
int main() {
  int n, q;
  scanf("%d%d", &n, &q);
  int lv = 0;
  while ((1 << lv) <= n) {
    lv++;
  }
  memset(t, 0, sizeof(t));
  memset(lazy, -1, sizeof(lazy));
  for (int i = 0; i < n; i++) {
    char ch;
    scanf(" %c", &ch);
    fill(1, (1 << lv) | i, (1 << lv) | (i + 1), lv, ch - 'a');
  }
  for (int i = 0; i < q; i++) {
    int l, r, op;
    scanf("%d%d%d", &l, &r, &op);
    l--;
    int got[CN];
    clear(got);
    query(1, (1 << lv) | l, (1 << lv) | r, lv, got);
    if (op == 1) {
      int begin = l;
      for (int ch = 0; ch < C; ch++) {
        fill(1, (1 << lv) | begin, (1 << lv) | (begin + got[ch]), lv, ch);
        begin += got[ch];
      }
    } else if (op == 0) {
      int begin = r;
      for (int ch = 0; ch < C; ch++) {
        fill(1, (1 << lv) | (begin - got[ch]), (1 << lv) | begin, lv, ch);
        begin -= got[ch];
      }
    }
  }
  for (int i = 0; i < n; i++) {
    int got[CN];
    clear(got);
    query(1, (1 << lv) | i, (1 << lv) | (i + 1), lv, got);
    for (int ch = 0; ch < C; ch++) {
      if (got[ch]) {
        putchar('a' + ch);
        break;
      }
    }
  }
  putchar('\n');
  return 0;
}

```