#include <bits/stdc++.h>
namespace chtholly {
inline int read() {
  int x = 0, f = 1;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f ^= c == '-';
  for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ '0');
  return f ? x : -x;
}
template <typename mitsuha>
inline bool read(mitsuha &x) {
  x = 0;
  int f = 1;
  char c = getchar();
  for (; !isdigit(c) && ~c; c = getchar()) f ^= c == '-';
  if (!~c) return 0;
  for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ '0');
  return x = f ? x : -x, 1;
}
template <typename mitsuha>
inline int write(mitsuha x) {
  if (!x) return putchar(48);
  if (x < 0) x = -x, putchar('-');
  int bit[20], i, p = 0;
  for (; x; x /= 10) bit[++p] = x % 10;
  for (i = p; i; --i) putchar(bit[i] + 48);
  return 0;
}
inline char fuhao() {
  char c = getchar();
  for (; isspace(c); c = getchar())
    ;
  return c;
}
}  // namespace chtholly
using namespace chtholly;
using namespace std;
const int yuzu = 1e5, _ = 26;
typedef int fuko[yuzu | 10];
char s[yuzu | 10];
int n = read(), q = read();
struct segtree {
  struct node {
    int d[_], cnt;
    bool sort, inc;
    void insert(int k) {
      memset(d, 0, sizeof d);
      cnt = d[k] = 1, sort = 0;
    }
    void bring(bool from, int sum) {
      cnt = sum;
      int i;
      if (from) {
        for (i = 0; i < _; ++i) {
          sum >= d[i] ? sum -= d[i] : (d[i] = sum, sum = 0);
        }
      } else {
        for (i = _ - 1; ~i; --i) {
          sum >= d[i] ? sum -= d[i] : (d[i] = sum, sum = 0);
        }
      }
    }
    void reng(bool from, int sum) {
      cnt -= sum;
      int i;
      if (from) {
        for (i = 0; i < _; ++i) {
          sum >= d[i] ? (sum -= d[i], d[i] = 0) : (d[i] -= sum, sum = 0);
        }
      } else {
        for (i = _ - 1; ~i; --i) {
          sum >= d[i] ? (sum -= d[i], d[i] = 0) : (d[i] -= sum, sum = 0);
        }
      }
    }
    node operator+(const node &b) const {
      node ans;
      ans.sort = 0;
      for (int i = 0; i < _; ++i) ans.d[i] = d[i] + b.d[i];
      ans.cnt = cnt + b.cnt;
      return ans;
    }
    void yuri() {
      printf("cnt=%d\n", cnt);
      for (int i = 0; i < _; ++i) {
        if (d[i]) printf("d[%d]=%d\n", i, d[i]);
      }
    }
  } tr[yuzu << 2 | 13];
  void push_down(int rt) {
    node &l = tr[rt << 1], &r = tr[rt << 1 | 1];
    if (tr[rt].sort) {
      int now = l.cnt;
      l = tr[rt], l.bring(tr[rt].inc, now);
      now = r.cnt;
      r = tr[rt], r.bring(!tr[rt].inc, now);
      tr[rt].sort = 0;
    }
  }
  void build(int rt = 1, int l = 1, int r = n) {
    if (l == r) return tr[rt].insert(s[l] - 'a');
    int mid = l + r >> 1;
    build(rt << 1, l, mid), build(rt << 1 | 1, mid + 1, r);
    tr[rt] = tr[rt << 1] + tr[rt << 1 | 1];
  }
  node query(int ql, int qr, int rt = 1, int l = 1, int r = n) {
    if (ql > r || qr < l) return node{{0}, 0, 0, 0};
    if (ql <= l && qr >= r) return tr[rt];
    push_down(rt);
    int mid = l + r >> 1;
    return query(ql, qr, rt << 1, l, mid) +
           query(ql, qr, rt << 1 | 1, mid + 1, r);
  }
  node sum;
  void update(int ql, int qr, int rt = 1, int l = 1, int r = n) {
    if (ql > r || qr < l) return;
    if (ql <= l && qr >= r) {
      int now = tr[rt].cnt;
      tr[rt] = sum;
      tr[rt].bring(sum.inc, now);
      sum.reng(sum.inc, now);
    } else {
      int mid = l + r >> 1;
      update(ql, qr, rt << 1, l, mid), update(ql, qr, rt << 1 | 1, mid + 1, r);
      tr[rt] = tr[rt << 1] + tr[rt << 1 | 1];
    }
  }
  void sortit(int l, int r, int inc) {
    sum = query(l, r), sum.sort = 1, sum.inc = inc;
    update(l, r);
  }
  void boom(int rt = 1, int l = 1, int r = n) {
    if (l == r) {
      for (int i = 0; i < _; ++i) {
        if (tr[rt].d[i]) {
          s[l] = i + 'a';
          break;
        }
      }
    } else {
      int mid = l + r >> 1;
      push_down(rt);
      boom(rt << 1, l, mid), boom(rt << 1 | 1, mid + 1, r);
    }
  }
  void dfs(int rt = 1, int l = 1, int r = n) {
    printf("#%d %d %d ", rt, l, r);
    tr[rt].yuri();
    int mid = l + r >> 1;
    if (l ^ r) dfs(rt << 1, l, mid), dfs(rt << 1 | 1, mid + 1, r);
  }
} my_;
int main() {
  scanf("%s", s + 1);
  my_.build();
  for (; q--;) {
    int l = read(), r = read();
    my_.sortit(l, r, read());
  }
  my_.boom();
  puts(s + 1);
}

### 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>
namespace chtholly {
inline int read() {
  int x = 0, f = 1;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f ^= c == '-';
  for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ '0');
  return f ? x : -x;
}
template <typename mitsuha>
inline bool read(mitsuha &x) {
  x = 0;
  int f = 1;
  char c = getchar();
  for (; !isdigit(c) && ~c; c = getchar()) f ^= c == '-';
  if (!~c) return 0;
  for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ '0');
  return x = f ? x : -x, 1;
}
template <typename mitsuha>
inline int write(mitsuha x) {
  if (!x) return putchar(48);
  if (x < 0) x = -x, putchar('-');
  int bit[20], i, p = 0;
  for (; x; x /= 10) bit[++p] = x % 10;
  for (i = p; i; --i) putchar(bit[i] + 48);
  return 0;
}
inline char fuhao() {
  char c = getchar();
  for (; isspace(c); c = getchar())
    ;
  return c;
}
}  // namespace chtholly
using namespace chtholly;
using namespace std;
const int yuzu = 1e5, _ = 26;
typedef int fuko[yuzu | 10];
char s[yuzu | 10];
int n = read(), q = read();
struct segtree {
  struct node {
    int d[_], cnt;
    bool sort, inc;
    void insert(int k) {
      memset(d, 0, sizeof d);
      cnt = d[k] = 1, sort = 0;
    }
    void bring(bool from, int sum) {
      cnt = sum;
      int i;
      if (from) {
        for (i = 0; i < _; ++i) {
          sum >= d[i] ? sum -= d[i] : (d[i] = sum, sum = 0);
        }
      } else {
        for (i = _ - 1; ~i; --i) {
          sum >= d[i] ? sum -= d[i] : (d[i] = sum, sum = 0);
        }
      }
    }
    void reng(bool from, int sum) {
      cnt -= sum;
      int i;
      if (from) {
        for (i = 0; i < _; ++i) {
          sum >= d[i] ? (sum -= d[i], d[i] = 0) : (d[i] -= sum, sum = 0);
        }
      } else {
        for (i = _ - 1; ~i; --i) {
          sum >= d[i] ? (sum -= d[i], d[i] = 0) : (d[i] -= sum, sum = 0);
        }
      }
    }
    node operator+(const node &b) const {
      node ans;
      ans.sort = 0;
      for (int i = 0; i < _; ++i) ans.d[i] = d[i] + b.d[i];
      ans.cnt = cnt + b.cnt;
      return ans;
    }
    void yuri() {
      printf("cnt=%d\n", cnt);
      for (int i = 0; i < _; ++i) {
        if (d[i]) printf("d[%d]=%d\n", i, d[i]);
      }
    }
  } tr[yuzu << 2 | 13];
  void push_down(int rt) {
    node &l = tr[rt << 1], &r = tr[rt << 1 | 1];
    if (tr[rt].sort) {
      int now = l.cnt;
      l = tr[rt], l.bring(tr[rt].inc, now);
      now = r.cnt;
      r = tr[rt], r.bring(!tr[rt].inc, now);
      tr[rt].sort = 0;
    }
  }
  void build(int rt = 1, int l = 1, int r = n) {
    if (l == r) return tr[rt].insert(s[l] - 'a');
    int mid = l + r >> 1;
    build(rt << 1, l, mid), build(rt << 1 | 1, mid + 1, r);
    tr[rt] = tr[rt << 1] + tr[rt << 1 | 1];
  }
  node query(int ql, int qr, int rt = 1, int l = 1, int r = n) {
    if (ql > r || qr < l) return node{{0}, 0, 0, 0};
    if (ql <= l && qr >= r) return tr[rt];
    push_down(rt);
    int mid = l + r >> 1;
    return query(ql, qr, rt << 1, l, mid) +
           query(ql, qr, rt << 1 | 1, mid + 1, r);
  }
  node sum;
  void update(int ql, int qr, int rt = 1, int l = 1, int r = n) {
    if (ql > r || qr < l) return;
    if (ql <= l && qr >= r) {
      int now = tr[rt].cnt;
      tr[rt] = sum;
      tr[rt].bring(sum.inc, now);
      sum.reng(sum.inc, now);
    } else {
      int mid = l + r >> 1;
      update(ql, qr, rt << 1, l, mid), update(ql, qr, rt << 1 | 1, mid + 1, r);
      tr[rt] = tr[rt << 1] + tr[rt << 1 | 1];
    }
  }
  void sortit(int l, int r, int inc) {
    sum = query(l, r), sum.sort = 1, sum.inc = inc;
    update(l, r);
  }
  void boom(int rt = 1, int l = 1, int r = n) {
    if (l == r) {
      for (int i = 0; i < _; ++i) {
        if (tr[rt].d[i]) {
          s[l] = i + 'a';
          break;
        }
      }
    } else {
      int mid = l + r >> 1;
      push_down(rt);
      boom(rt << 1, l, mid), boom(rt << 1 | 1, mid + 1, r);
    }
  }
  void dfs(int rt = 1, int l = 1, int r = n) {
    printf("#%d %d %d ", rt, l, r);
    tr[rt].yuri();
    int mid = l + r >> 1;
    if (l ^ r) dfs(rt << 1, l, mid), dfs(rt << 1 | 1, mid + 1, r);
  }
} my_;
int main() {
  scanf("%s", s + 1);
  my_.build();
  for (; q--;) {
    int l = read(), r = read();
    my_.sortit(l, r, read());
  }
  my_.boom();
  puts(s + 1);
}

```