#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, q, lgrup, ngrup, c[320][26], is[320];
char s[N];
void update(int no) {
  if (is[no] == 0) return;
  int now, cnt[26], nloop = min(lgrup, n - no * lgrup);
  for (int i = 0; i < 26; i++) cnt[i] = c[no][i];
  if (is[no] == 1) {
    now = 0;
    for (int i = 0; i < nloop; i++) {
      while (cnt[now] == 0) now++;
      s[i + no * lgrup] = now + 'a';
      cnt[now]--;
    }
  } else {
    now = 25;
    for (int i = 0; i < nloop; i++) {
      while (cnt[now] == 0) now--;
      s[i + no * lgrup] = now + 'a';
      cnt[now]--;
    }
  }
  is[no] = 0;
}
void getCount(int x, int y, int* cnt) {
  for (int i = 0; i < 26; i++) cnt[i] = 0;
  int lg, rg;
  if (x / lgrup == y / lgrup) {
    for (int i = x; i <= y; i++) cnt[s[i] - 'a']++;
    return;
  }
  if (x % lgrup) {
    lg = x / lgrup + 1;
    for (int i = x; i < lg * lgrup; i++) cnt[s[i] - 'a']++;
  } else
    lg = x / lgrup;
  if ((y + 1) % lgrup) {
    rg = y / lgrup;
    for (int i = rg * lgrup; i <= y; i++) cnt[s[i] - 'a']++;
    rg--;
  } else
    rg = y / lgrup;
  for (int i = lg; i <= rg; i++)
    for (int j = 0; j < 26; j++) cnt[j] += c[i][j];
}
int main() {
  scanf("%d%d", &n, &q);
  scanf("%s", s);
  lgrup = sqrt(n);
  ngrup = (n + lgrup - 1) / lgrup;
  memset(is, 0, sizeof is);
  memset(c, 0, sizeof c);
  for (int i = 0; i < n; i++) c[i / lgrup][s[i] - 'a']++;
  while (q--) {
    int x, y, z, lg, rg, now;
    int cnt[26];
    scanf("%d%d%d", &x, &y, &z);
    x--;
    y--;
    if (x % lgrup) update(x / lgrup);
    if ((y + 1) % lgrup) update(y / lgrup);
    getCount(x, y, cnt);
    if (z)
      now = 0;
    else
      now = 25;
    if (x / lgrup == y / lgrup) {
      lg = x / lgrup;
      for (int i = x; i <= y; i++) {
        while (cnt[now] == 0 && now >= 0 && now < 26)
          if (z)
            now++;
          else
            now--;
        c[lg][s[i] - 'a']--;
        s[i] = 'a' + now;
        c[lg][now]++;
        cnt[now]--;
      }
      continue;
    }
    if (x % lgrup) {
      lg = x / lgrup + 1;
      for (int i = x; i < lg * lgrup; i++) {
        while (cnt[now] == 0 && now >= 0 && now < 26)
          if (z)
            now++;
          else
            now--;
        c[lg - 1][s[i] - 'a']--;
        s[i] = 'a' + now;
        c[lg - 1][now]++;
        cnt[now]--;
      }
    } else
      lg = x / lgrup;
    rg = (y + 1) / lgrup;
    for (int i = lg; i < rg; i++) {
      int cur = lgrup;
      memset(c[i], 0, sizeof c[i]);
      while (cur) {
        while (cnt[now] == 0 && now >= 0 && now < 26)
          if (z)
            now++;
          else
            now--;
        int red = min(cur, cnt[now]);
        c[i][now] += red;
        cur -= red;
        cnt[now] -= red;
      }
      is[i] = (z ? 1 : -1);
    }
    for (int i = rg * lgrup; i <= y; i++) {
      while (cnt[now] == 0 && now >= 0 && now < 26)
        if (z)
          now++;
        else
          now--;
      c[rg][s[i] - 'a']--;
      s[i] = 'a' + now;
      c[rg][now]++;
      cnt[now]--;
    }
  }
  for (int i = 0; i < ngrup; i++) update(i);
  printf("%s\n", s);
  return 0;
}

### Prompt

Create a solution in Cpp for 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;
const int N = 1e5 + 5;
int n, q, lgrup, ngrup, c[320][26], is[320];
char s[N];
void update(int no) {
  if (is[no] == 0) return;
  int now, cnt[26], nloop = min(lgrup, n - no * lgrup);
  for (int i = 0; i < 26; i++) cnt[i] = c[no][i];
  if (is[no] == 1) {
    now = 0;
    for (int i = 0; i < nloop; i++) {
      while (cnt[now] == 0) now++;
      s[i + no * lgrup] = now + 'a';
      cnt[now]--;
    }
  } else {
    now = 25;
    for (int i = 0; i < nloop; i++) {
      while (cnt[now] == 0) now--;
      s[i + no * lgrup] = now + 'a';
      cnt[now]--;
    }
  }
  is[no] = 0;
}
void getCount(int x, int y, int* cnt) {
  for (int i = 0; i < 26; i++) cnt[i] = 0;
  int lg, rg;
  if (x / lgrup == y / lgrup) {
    for (int i = x; i <= y; i++) cnt[s[i] - 'a']++;
    return;
  }
  if (x % lgrup) {
    lg = x / lgrup + 1;
    for (int i = x; i < lg * lgrup; i++) cnt[s[i] - 'a']++;
  } else
    lg = x / lgrup;
  if ((y + 1) % lgrup) {
    rg = y / lgrup;
    for (int i = rg * lgrup; i <= y; i++) cnt[s[i] - 'a']++;
    rg--;
  } else
    rg = y / lgrup;
  for (int i = lg; i <= rg; i++)
    for (int j = 0; j < 26; j++) cnt[j] += c[i][j];
}
int main() {
  scanf("%d%d", &n, &q);
  scanf("%s", s);
  lgrup = sqrt(n);
  ngrup = (n + lgrup - 1) / lgrup;
  memset(is, 0, sizeof is);
  memset(c, 0, sizeof c);
  for (int i = 0; i < n; i++) c[i / lgrup][s[i] - 'a']++;
  while (q--) {
    int x, y, z, lg, rg, now;
    int cnt[26];
    scanf("%d%d%d", &x, &y, &z);
    x--;
    y--;
    if (x % lgrup) update(x / lgrup);
    if ((y + 1) % lgrup) update(y / lgrup);
    getCount(x, y, cnt);
    if (z)
      now = 0;
    else
      now = 25;
    if (x / lgrup == y / lgrup) {
      lg = x / lgrup;
      for (int i = x; i <= y; i++) {
        while (cnt[now] == 0 && now >= 0 && now < 26)
          if (z)
            now++;
          else
            now--;
        c[lg][s[i] - 'a']--;
        s[i] = 'a' + now;
        c[lg][now]++;
        cnt[now]--;
      }
      continue;
    }
    if (x % lgrup) {
      lg = x / lgrup + 1;
      for (int i = x; i < lg * lgrup; i++) {
        while (cnt[now] == 0 && now >= 0 && now < 26)
          if (z)
            now++;
          else
            now--;
        c[lg - 1][s[i] - 'a']--;
        s[i] = 'a' + now;
        c[lg - 1][now]++;
        cnt[now]--;
      }
    } else
      lg = x / lgrup;
    rg = (y + 1) / lgrup;
    for (int i = lg; i < rg; i++) {
      int cur = lgrup;
      memset(c[i], 0, sizeof c[i]);
      while (cur) {
        while (cnt[now] == 0 && now >= 0 && now < 26)
          if (z)
            now++;
          else
            now--;
        int red = min(cur, cnt[now]);
        c[i][now] += red;
        cur -= red;
        cnt[now] -= red;
      }
      is[i] = (z ? 1 : -1);
    }
    for (int i = rg * lgrup; i <= y; i++) {
      while (cnt[now] == 0 && now >= 0 && now < 26)
        if (z)
          now++;
        else
          now--;
      c[rg][s[i] - 'a']--;
      s[i] = 'a' + now;
      c[rg][now]++;
      cnt[now]--;
    }
  }
  for (int i = 0; i < ngrup; i++) update(i);
  printf("%s\n", s);
  return 0;
}

```