#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x) {
  x = 0;
  char c = getchar();
  bool flag = false;
  while (!isdigit(c)) {
    if (c == '-') flag = true;
    c = getchar();
  }
  while (isdigit(c)) {
    x = (x << 1) + (x << 3) + (c ^ 48);
    c = getchar();
  }
  if (flag) x = -x;
}
int n, m, root = 1;
char str[400010];
struct node {
  int s[30];
  node() { memset(s, 0, sizeof(s)); }
} sum[400010], tag[400010];
node operator+(const node &a, const node &b) {
  node c;
  for (int i = 1; i <= 26; ++i) c.s[i] = a.s[i] + b.s[i];
  return c;
}
void pushup(int cur) { sum[cur] = sum[(cur << 1)] + sum[(cur << 1 | 1)]; }
void pushtag(int cur, int id, int l, int r) {
  node t;
  sum[cur] = tag[cur] = t;
  sum[cur].s[id] = r - l + 1, tag[cur].s[id] = 1;
}
void pushdown(int cur, int l, int r) {
  for (int i = 1; i <= 26; ++i) {
    if (tag[cur].s[i]) {
      pushtag((cur << 1), i, l, ((l + r) >> 1)),
          pushtag((cur << 1 | 1), i, ((l + r) >> 1) + 1, r);
      tag[cur].s[i] = 0;
      return;
    }
  }
}
void build(int l, int r, int cur) {
  if (l == r) {
    sum[cur].s[str[l] - 'a' + 1]++;
    return;
  }
  build(l, ((l + r) >> 1), (cur << 1)),
      build(((l + r) >> 1) + 1, r, (cur << 1 | 1));
  pushup(cur);
}
void modify(int L, int R, int l, int r, int id, int cur) {
  if (L <= l && R >= r) {
    pushtag(cur, id, l, r);
    return;
  }
  pushdown(cur, l, r);
  if (L <= ((l + r) >> 1)) modify(L, R, l, ((l + r) >> 1), id, (cur << 1));
  if (R > ((l + r) >> 1))
    modify(L, R, ((l + r) >> 1) + 1, r, id, (cur << 1 | 1));
  pushup(cur);
}
node query(int L, int R, int l, int r, int cur) {
  if (L <= l && R >= r) return sum[cur];
  node ans;
  pushdown(cur, l, r);
  if (L <= ((l + r) >> 1))
    ans = ans + query(L, R, l, ((l + r) >> 1), (cur << 1));
  if (R > ((l + r) >> 1))
    ans = ans + query(L, R, ((l + r) >> 1) + 1, r, (cur << 1 | 1));
  return ans;
}
void dfs(int l, int r, int cur) {
  if (l == r) {
    for (int i = 1; i <= 26; ++i) {
      if (sum[cur].s[i]) {
        str[l] = 'a' + i - 1;
        return;
      }
    }
  }
  pushdown(cur, l, r);
  dfs(l, ((l + r) >> 1), (cur << 1)),
      dfs(((l + r) >> 1) + 1, r, (cur << 1 | 1));
}
int main() {
  read(n), read(m);
  scanf("%s", str + 1), build(1, n, root);
  while (m--) {
    int opt, l, r;
    read(l), read(r), read(opt);
    node q = query(l, r, 1, n, root);
    if (opt == 1) {
      for (int i = 1; i <= 26; ++i) {
        if (!q.s[i]) continue;
        modify(l, l + q.s[i] - 1, 1, n, i, root), l += q.s[i];
      }
    } else {
      for (int i = 26; i; --i) {
        if (!q.s[i]) continue;
        modify(l, l + q.s[i] - 1, 1, n, i, root), l += q.s[i];
      }
    }
  }
  dfs(1, n, root);
  printf("%s", str + 1);
  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;
template <typename T>
inline void read(T &x) {
  x = 0;
  char c = getchar();
  bool flag = false;
  while (!isdigit(c)) {
    if (c == '-') flag = true;
    c = getchar();
  }
  while (isdigit(c)) {
    x = (x << 1) + (x << 3) + (c ^ 48);
    c = getchar();
  }
  if (flag) x = -x;
}
int n, m, root = 1;
char str[400010];
struct node {
  int s[30];
  node() { memset(s, 0, sizeof(s)); }
} sum[400010], tag[400010];
node operator+(const node &a, const node &b) {
  node c;
  for (int i = 1; i <= 26; ++i) c.s[i] = a.s[i] + b.s[i];
  return c;
}
void pushup(int cur) { sum[cur] = sum[(cur << 1)] + sum[(cur << 1 | 1)]; }
void pushtag(int cur, int id, int l, int r) {
  node t;
  sum[cur] = tag[cur] = t;
  sum[cur].s[id] = r - l + 1, tag[cur].s[id] = 1;
}
void pushdown(int cur, int l, int r) {
  for (int i = 1; i <= 26; ++i) {
    if (tag[cur].s[i]) {
      pushtag((cur << 1), i, l, ((l + r) >> 1)),
          pushtag((cur << 1 | 1), i, ((l + r) >> 1) + 1, r);
      tag[cur].s[i] = 0;
      return;
    }
  }
}
void build(int l, int r, int cur) {
  if (l == r) {
    sum[cur].s[str[l] - 'a' + 1]++;
    return;
  }
  build(l, ((l + r) >> 1), (cur << 1)),
      build(((l + r) >> 1) + 1, r, (cur << 1 | 1));
  pushup(cur);
}
void modify(int L, int R, int l, int r, int id, int cur) {
  if (L <= l && R >= r) {
    pushtag(cur, id, l, r);
    return;
  }
  pushdown(cur, l, r);
  if (L <= ((l + r) >> 1)) modify(L, R, l, ((l + r) >> 1), id, (cur << 1));
  if (R > ((l + r) >> 1))
    modify(L, R, ((l + r) >> 1) + 1, r, id, (cur << 1 | 1));
  pushup(cur);
}
node query(int L, int R, int l, int r, int cur) {
  if (L <= l && R >= r) return sum[cur];
  node ans;
  pushdown(cur, l, r);
  if (L <= ((l + r) >> 1))
    ans = ans + query(L, R, l, ((l + r) >> 1), (cur << 1));
  if (R > ((l + r) >> 1))
    ans = ans + query(L, R, ((l + r) >> 1) + 1, r, (cur << 1 | 1));
  return ans;
}
void dfs(int l, int r, int cur) {
  if (l == r) {
    for (int i = 1; i <= 26; ++i) {
      if (sum[cur].s[i]) {
        str[l] = 'a' + i - 1;
        return;
      }
    }
  }
  pushdown(cur, l, r);
  dfs(l, ((l + r) >> 1), (cur << 1)),
      dfs(((l + r) >> 1) + 1, r, (cur << 1 | 1));
}
int main() {
  read(n), read(m);
  scanf("%s", str + 1), build(1, n, root);
  while (m--) {
    int opt, l, r;
    read(l), read(r), read(opt);
    node q = query(l, r, 1, n, root);
    if (opt == 1) {
      for (int i = 1; i <= 26; ++i) {
        if (!q.s[i]) continue;
        modify(l, l + q.s[i] - 1, 1, n, i, root), l += q.s[i];
      }
    } else {
      for (int i = 26; i; --i) {
        if (!q.s[i]) continue;
        modify(l, l + q.s[i] - 1, 1, n, i, root), l += q.s[i];
      }
    }
  }
  dfs(1, n, root);
  printf("%s", str + 1);
  return 0;
}

```