#include <bits/stdc++.h>
struct Area {
  int l, r;
  int lzt;
  int has[30];
} p[200000];
int n, q;
int a[200000];
int blg[200000];
int tmp[30];
char cmd[1000000];
bool cmp(int x, int y) { return x < y; }
bool cmq(int x, int y) { return x > y; }
void P_sort(int x) {
  if (!p[x].lzt) return;
  if (p[x].lzt == 1) {
    int t = 1;
    for (int i = p[x].l; i <= p[x].r; i++) {
      while (!p[x].has[t]) t++;
      a[i] = t;
      p[x].has[t]--;
    }
  }
  if (p[x].lzt == -1) {
    int t = 26;
    for (int i = p[x].l; i <= p[x].r; i++) {
      while (!p[x].has[t]) t--;
      a[i] = t;
      p[x].has[t]--;
    }
  }
  p[x].lzt = 0;
  return;
}
void build(int x) {
  for (int i = 1; i <= 26; i++) p[x].has[i] = 0;
  for (int i = p[x].l; i <= p[x].r; i++) p[x].has[a[i]]++;
  return;
}
int main() {
  scanf("%d%d", &n, &q);
  if (n <= 1000) {
    scanf("%s", cmd + 1);
    for (int i = 1; i <= n; i++) a[i] = cmd[i] - 'a' + 1;
    for (int i = 1; i <= q; i++) {
      int l, r, op;
      scanf("%d%d%d", &l, &r, &op);
      if (l > r) std::swap(l, r);
      if (op == 0)
        std::sort(a + l, a + r + 1, cmq);
      else
        std::sort(a + l, a + r + 1, cmp);
    }
    for (int i = 1; i <= n; i++) printf("%c", a[i] + 'a' - 1);
    puts("");
    return 0;
  }
  scanf("%s", cmd + 1);
  int stan = (sqrt(n));
  for (int i = 1; i <= n; i++) {
    a[i] = cmd[i] - 'a' + 1;
    blg[i] = i / stan + 1;
    p[blg[i]].has[a[i]]++;
    if (blg[i] != blg[i - 1]) {
      p[blg[i]].l = i;
      p[blg[i - 1]].r = i - 1;
    }
  }
  p[blg[n]].r = n;
  while (q--) {
    int l, r, op;
    scanf("%d%d%d", &l, &r, &op);
    if (l > r) std::swap(l, r);
    if (blg[l] == blg[r]) {
      if (op == 0)
        std::sort(a + l, a + r + 1, cmq);
      else
        std::sort(a + l, a + r + 1, cmp);
      continue;
    }
    memset(tmp, 0, sizeof(tmp));
    P_sort(blg[l]);
    build(blg[l]);
    P_sort(blg[r]);
    build(blg[r]);
    for (int i = l; i <= p[blg[l]].r; i++) tmp[a[i]]++;
    for (int i = p[blg[r]].l; i <= r; i++) tmp[a[i]]++;
    for (int i = 1; i <= 26; i++)
      for (int j = blg[l] + 1; j <= blg[r] - 1; j++) tmp[i] += p[j].has[i];
    if (op == 0) {
      int t = 26;
      for (int i = l; i <= p[blg[l]].r; i++) {
        while (!tmp[t]) t--;
        tmp[t]--;
        a[i] = t;
      }
      build(blg[l]);
      for (int i = blg[l] + 1; i <= blg[r] - 1; i++) {
        int len = p[i].r - p[i].l + 1;
        for (int j = 1; j <= 26; j++) p[i].has[j] = 0;
        while (tmp[t] < len) {
          p[i].has[t] += tmp[t];
          len -= tmp[t];
          tmp[t] = 0;
          t--;
        }
        if (len) {
          p[i].has[t] += len;
          tmp[t] -= len;
          if (!tmp[t]) t--;
        }
        p[i].lzt = -1;
      }
      for (int i = p[blg[r]].l; i <= r; i++) {
        while (!tmp[t]) t--;
        tmp[t]--;
        a[i] = t;
      }
      build(blg[r]);
    } else {
      int t = 1;
      for (int i = l; i <= p[blg[l]].r; i++) {
        while (!tmp[t]) t++;
        tmp[t]--;
        a[i] = t;
      }
      build(blg[l]);
      for (int i = blg[l] + 1; i <= blg[r] - 1; i++) {
        int len = p[i].r - p[i].l + 1;
        for (int j = 1; j <= 26; j++) p[i].has[j] = 0;
        while (tmp[t] < len) {
          p[i].has[t] += tmp[t];
          len -= tmp[t];
          tmp[t] = 0;
          t++;
        }
        if (len) {
          p[i].has[t] += len;
          tmp[t] -= len;
          if (!tmp[t]) t++;
        }
        p[i].lzt = 1;
      }
      for (int i = p[blg[r]].l; i <= r; i++) {
        while (!tmp[t]) t++;
        tmp[t]--;
        a[i] = t;
      }
      build(blg[r]);
    }
  }
  for (int i = 1; i <= blg[n]; i++) P_sort(i);
  for (int i = 1; i <= n; i++) printf("%c", a[i] + 'a' - 1);
  puts("");
  return 0;
}

### Prompt

Please create a solution in cpp to 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>
struct Area {
  int l, r;
  int lzt;
  int has[30];
} p[200000];
int n, q;
int a[200000];
int blg[200000];
int tmp[30];
char cmd[1000000];
bool cmp(int x, int y) { return x < y; }
bool cmq(int x, int y) { return x > y; }
void P_sort(int x) {
  if (!p[x].lzt) return;
  if (p[x].lzt == 1) {
    int t = 1;
    for (int i = p[x].l; i <= p[x].r; i++) {
      while (!p[x].has[t]) t++;
      a[i] = t;
      p[x].has[t]--;
    }
  }
  if (p[x].lzt == -1) {
    int t = 26;
    for (int i = p[x].l; i <= p[x].r; i++) {
      while (!p[x].has[t]) t--;
      a[i] = t;
      p[x].has[t]--;
    }
  }
  p[x].lzt = 0;
  return;
}
void build(int x) {
  for (int i = 1; i <= 26; i++) p[x].has[i] = 0;
  for (int i = p[x].l; i <= p[x].r; i++) p[x].has[a[i]]++;
  return;
}
int main() {
  scanf("%d%d", &n, &q);
  if (n <= 1000) {
    scanf("%s", cmd + 1);
    for (int i = 1; i <= n; i++) a[i] = cmd[i] - 'a' + 1;
    for (int i = 1; i <= q; i++) {
      int l, r, op;
      scanf("%d%d%d", &l, &r, &op);
      if (l > r) std::swap(l, r);
      if (op == 0)
        std::sort(a + l, a + r + 1, cmq);
      else
        std::sort(a + l, a + r + 1, cmp);
    }
    for (int i = 1; i <= n; i++) printf("%c", a[i] + 'a' - 1);
    puts("");
    return 0;
  }
  scanf("%s", cmd + 1);
  int stan = (sqrt(n));
  for (int i = 1; i <= n; i++) {
    a[i] = cmd[i] - 'a' + 1;
    blg[i] = i / stan + 1;
    p[blg[i]].has[a[i]]++;
    if (blg[i] != blg[i - 1]) {
      p[blg[i]].l = i;
      p[blg[i - 1]].r = i - 1;
    }
  }
  p[blg[n]].r = n;
  while (q--) {
    int l, r, op;
    scanf("%d%d%d", &l, &r, &op);
    if (l > r) std::swap(l, r);
    if (blg[l] == blg[r]) {
      if (op == 0)
        std::sort(a + l, a + r + 1, cmq);
      else
        std::sort(a + l, a + r + 1, cmp);
      continue;
    }
    memset(tmp, 0, sizeof(tmp));
    P_sort(blg[l]);
    build(blg[l]);
    P_sort(blg[r]);
    build(blg[r]);
    for (int i = l; i <= p[blg[l]].r; i++) tmp[a[i]]++;
    for (int i = p[blg[r]].l; i <= r; i++) tmp[a[i]]++;
    for (int i = 1; i <= 26; i++)
      for (int j = blg[l] + 1; j <= blg[r] - 1; j++) tmp[i] += p[j].has[i];
    if (op == 0) {
      int t = 26;
      for (int i = l; i <= p[blg[l]].r; i++) {
        while (!tmp[t]) t--;
        tmp[t]--;
        a[i] = t;
      }
      build(blg[l]);
      for (int i = blg[l] + 1; i <= blg[r] - 1; i++) {
        int len = p[i].r - p[i].l + 1;
        for (int j = 1; j <= 26; j++) p[i].has[j] = 0;
        while (tmp[t] < len) {
          p[i].has[t] += tmp[t];
          len -= tmp[t];
          tmp[t] = 0;
          t--;
        }
        if (len) {
          p[i].has[t] += len;
          tmp[t] -= len;
          if (!tmp[t]) t--;
        }
        p[i].lzt = -1;
      }
      for (int i = p[blg[r]].l; i <= r; i++) {
        while (!tmp[t]) t--;
        tmp[t]--;
        a[i] = t;
      }
      build(blg[r]);
    } else {
      int t = 1;
      for (int i = l; i <= p[blg[l]].r; i++) {
        while (!tmp[t]) t++;
        tmp[t]--;
        a[i] = t;
      }
      build(blg[l]);
      for (int i = blg[l] + 1; i <= blg[r] - 1; i++) {
        int len = p[i].r - p[i].l + 1;
        for (int j = 1; j <= 26; j++) p[i].has[j] = 0;
        while (tmp[t] < len) {
          p[i].has[t] += tmp[t];
          len -= tmp[t];
          tmp[t] = 0;
          t++;
        }
        if (len) {
          p[i].has[t] += len;
          tmp[t] -= len;
          if (!tmp[t]) t++;
        }
        p[i].lzt = 1;
      }
      for (int i = p[blg[r]].l; i <= r; i++) {
        while (!tmp[t]) t++;
        tmp[t]--;
        a[i] = t;
      }
      build(blg[r]);
    }
  }
  for (int i = 1; i <= blg[n]; i++) P_sort(i);
  for (int i = 1; i <= n; i++) printf("%c", a[i] + 'a' - 1);
  puts("");
  return 0;
}

```