#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1);
inline bool EQ(double a, double b) { return fabs(a - b) < 1e-9; }
long long add(long long a, long long b) {
  long long ret = a + b;
  if (ret >= 1000000007) ret -= 1000000007;
  return ret;
}
long long subtract(long long a, long long b) {
  long long ret = a - b;
  if (ret < 0) ret += 1000000007;
  return ret;
}
long long mult(long long a, long long b) {
  long long ret = a * b;
  if (ret >= 1000000007) ret %= 1000000007;
  return ret;
}
long long bigmod(long long a, long long b) {
  long long ret = 1;
  while (b) {
    if (b & 1) ret = mult(ret, a);
    b >>= 1;
    a = mult(a, a);
  }
  return ret;
}
long long inverse(long long n) { return bigmod(n, 1000000007 - 2); }
bool base[1000010];
vector<int> primes;
void sieve(int mx) {
  mx += 10;
  int x = sqrt(mx);
  for (int i = 3; i <= x; i += 2)
    if (base[i] == 0)
      for (int j = i * i, k = i << 1; j < mx; j += k) base[j] = 1;
  primes.push_back(2);
  for (int i = 3; i < mx; i += 2)
    if (base[i] == 0) primes.push_back(i);
}
bool checkBit(int n, int i) { return (n & (1 << i)); }
int setBit(int n, int i) { return (n | (1 << i)); }
int resetBit(int n, int i) { return (n & (~(1 << i))); }
int tree[100010 << 2][26], lazy[100010 << 2], cnt[26];
char a[100010];
void build(int node, int l, int h) {
  lazy[node] = -1;
  if (l == h) {
    ++tree[node][a[l] - 'a'];
    return;
  }
  int m = (l + h) / 2;
  build((node << 1), l, m);
  build(((node << 1) | 1), m + 1, h);
  for (int i = 0; i < 26; ++i)
    tree[node][i] = tree[(node << 1)][i] + tree[((node << 1) | 1)][i];
}
void update_node(int node, int ch, int l, int h) {
  for (int i = 0; i < 26; ++i) tree[node][i] = 0;
  tree[node][ch] = h - l + 1;
  lazy[node] = ch;
}
void push(int node, int l, int h) {
  if (lazy[node] != -1) {
    int m = (l + h) / 2;
    update_node((node << 1), lazy[node], l, m);
    update_node(((node << 1) | 1), lazy[node], m + 1, h);
    lazy[node] = -1;
  }
}
void query(int node, int l, int h, int i, int j) {
  if (i == l && j == h) {
    for (int k = 0; k < 26; ++k) cnt[k] += tree[node][k];
    return;
  }
  push(node, l, h);
  int m = (l + h) / 2;
  if (j <= m)
    query((node << 1), l, m, i, j);
  else if (i > m)
    query(((node << 1) | 1), m + 1, h, i, j);
  else {
    query((node << 1), l, m, i, m);
    query(((node << 1) | 1), m + 1, h, m + 1, j);
  }
}
void update(int node, int l, int h, int i, int j, int ch) {
  if (i == l && j == h) {
    update_node(node, ch, l, h);
    return;
  }
  push(node, l, h);
  int m = (l + h) / 2;
  if (j <= m)
    update((node << 1), l, m, i, j, ch);
  else if (i > m)
    update(((node << 1) | 1), m + 1, h, i, j, ch);
  else {
    update((node << 1), l, m, i, m, ch);
    update(((node << 1) | 1), m + 1, h, m + 1, j, ch);
  }
  for (int k = 0; k < 26; ++k)
    tree[node][k] = tree[(node << 1)][k] + tree[((node << 1) | 1)][k];
}
int main() {
  int n, q, l, r, k;
  scanf("%d%d", &n, &q);
  scanf("%s", a + 1);
  build(1, 1, n);
  while (q--) {
    scanf("%d%d%d", &l, &r, &k);
    for (int i = 0; i < 26; ++i) cnt[i] = 0;
    query(1, 1, n, l, r);
    if (k == 1) {
      int curr = l;
      for (int i = 0; i < 26; ++i)
        if (cnt[i]) {
          update(1, 1, n, curr, curr + cnt[i] - 1, i);
          curr += cnt[i];
        }
    } else {
      int curr = l;
      for (int i = 25; i >= 0; --i)
        if (cnt[i]) {
          update(1, 1, n, curr, curr + cnt[i] - 1, i);
          curr += cnt[i];
        }
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < 26; ++j) cnt[j] = 0;
    query(1, 1, n, i, i);
    for (int j = 0; j < 26; ++j)
      if (cnt[j]) {
        printf("%c", (char)(j + 'a'));
        break;
      }
  }
  puts("");
  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;
const double PI = acos(-1);
inline bool EQ(double a, double b) { return fabs(a - b) < 1e-9; }
long long add(long long a, long long b) {
  long long ret = a + b;
  if (ret >= 1000000007) ret -= 1000000007;
  return ret;
}
long long subtract(long long a, long long b) {
  long long ret = a - b;
  if (ret < 0) ret += 1000000007;
  return ret;
}
long long mult(long long a, long long b) {
  long long ret = a * b;
  if (ret >= 1000000007) ret %= 1000000007;
  return ret;
}
long long bigmod(long long a, long long b) {
  long long ret = 1;
  while (b) {
    if (b & 1) ret = mult(ret, a);
    b >>= 1;
    a = mult(a, a);
  }
  return ret;
}
long long inverse(long long n) { return bigmod(n, 1000000007 - 2); }
bool base[1000010];
vector<int> primes;
void sieve(int mx) {
  mx += 10;
  int x = sqrt(mx);
  for (int i = 3; i <= x; i += 2)
    if (base[i] == 0)
      for (int j = i * i, k = i << 1; j < mx; j += k) base[j] = 1;
  primes.push_back(2);
  for (int i = 3; i < mx; i += 2)
    if (base[i] == 0) primes.push_back(i);
}
bool checkBit(int n, int i) { return (n & (1 << i)); }
int setBit(int n, int i) { return (n | (1 << i)); }
int resetBit(int n, int i) { return (n & (~(1 << i))); }
int tree[100010 << 2][26], lazy[100010 << 2], cnt[26];
char a[100010];
void build(int node, int l, int h) {
  lazy[node] = -1;
  if (l == h) {
    ++tree[node][a[l] - 'a'];
    return;
  }
  int m = (l + h) / 2;
  build((node << 1), l, m);
  build(((node << 1) | 1), m + 1, h);
  for (int i = 0; i < 26; ++i)
    tree[node][i] = tree[(node << 1)][i] + tree[((node << 1) | 1)][i];
}
void update_node(int node, int ch, int l, int h) {
  for (int i = 0; i < 26; ++i) tree[node][i] = 0;
  tree[node][ch] = h - l + 1;
  lazy[node] = ch;
}
void push(int node, int l, int h) {
  if (lazy[node] != -1) {
    int m = (l + h) / 2;
    update_node((node << 1), lazy[node], l, m);
    update_node(((node << 1) | 1), lazy[node], m + 1, h);
    lazy[node] = -1;
  }
}
void query(int node, int l, int h, int i, int j) {
  if (i == l && j == h) {
    for (int k = 0; k < 26; ++k) cnt[k] += tree[node][k];
    return;
  }
  push(node, l, h);
  int m = (l + h) / 2;
  if (j <= m)
    query((node << 1), l, m, i, j);
  else if (i > m)
    query(((node << 1) | 1), m + 1, h, i, j);
  else {
    query((node << 1), l, m, i, m);
    query(((node << 1) | 1), m + 1, h, m + 1, j);
  }
}
void update(int node, int l, int h, int i, int j, int ch) {
  if (i == l && j == h) {
    update_node(node, ch, l, h);
    return;
  }
  push(node, l, h);
  int m = (l + h) / 2;
  if (j <= m)
    update((node << 1), l, m, i, j, ch);
  else if (i > m)
    update(((node << 1) | 1), m + 1, h, i, j, ch);
  else {
    update((node << 1), l, m, i, m, ch);
    update(((node << 1) | 1), m + 1, h, m + 1, j, ch);
  }
  for (int k = 0; k < 26; ++k)
    tree[node][k] = tree[(node << 1)][k] + tree[((node << 1) | 1)][k];
}
int main() {
  int n, q, l, r, k;
  scanf("%d%d", &n, &q);
  scanf("%s", a + 1);
  build(1, 1, n);
  while (q--) {
    scanf("%d%d%d", &l, &r, &k);
    for (int i = 0; i < 26; ++i) cnt[i] = 0;
    query(1, 1, n, l, r);
    if (k == 1) {
      int curr = l;
      for (int i = 0; i < 26; ++i)
        if (cnt[i]) {
          update(1, 1, n, curr, curr + cnt[i] - 1, i);
          curr += cnt[i];
        }
    } else {
      int curr = l;
      for (int i = 25; i >= 0; --i)
        if (cnt[i]) {
          update(1, 1, n, curr, curr + cnt[i] - 1, i);
          curr += cnt[i];
        }
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < 26; ++j) cnt[j] = 0;
    query(1, 1, n, i, i);
    for (int j = 0; j < 26; ++j)
      if (cnt[j]) {
        printf("%c", (char)(j + 'a'));
        break;
      }
  }
  puts("");
  return 0;
}

```