#include <bits/stdc++.h>
using namespace std;
inline long long getnum() {
  char c = getchar();
  long long num, sign = 1;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') sign = -1;
  for (num = 0; c >= '0' && c <= '9';) {
    c -= '0';
    num = num * 10 + c;
    c = getchar();
  }
  return num * sign;
}
char S[100006];
int A[100006], B[100006];
int Tree[30][100006 * 3 * 2];
int Lazy[30][100006 * 3 * 2];
int create(int l, int r, int ind, int c) {
  if (l == r) {
    if (A[l] == c)
      Tree[c][ind] = 1;
    else
      Tree[c][ind] = 0;
    return Tree[c][ind];
  }
  int x = (l + r) / 2;
  Tree[c][ind] = create(l, x, 2 * ind, c) + create(x + 1, r, 2 * ind + 1, c);
  return Tree[c][ind];
}
int get(int l, int r, int lx, int rx, int ind, int c) {
  int x = (l + r) / 2;
  if (Lazy[c][ind] != -1) {
    Tree[c][2 * ind] = min(Lazy[c][ind], x - l + 1);
    Tree[c][2 * ind + 1] = min(Lazy[c][ind], r - x);
    Lazy[c][2 * ind] = Tree[c][2 * ind];
    Lazy[c][2 * ind + 1] = Tree[c][2 * ind + 1];
  }
  Lazy[c][ind] = -1;
  if (l == lx && r == rx) {
    return Tree[c][ind];
  }
  if (rx <= x)
    return get(l, x, lx, rx, 2 * ind, c);
  else if (lx > x)
    return get(x + 1, r, lx, rx, 2 * ind + 1, c);
  else
    return get(l, x, lx, x, 2 * ind, c) +
           get(x + 1, r, x + 1, rx, 2 * ind + 1, c);
}
int update(int l, int r, int lx, int rx, int cnt, int ind, int c) {
  if (lx > rx) return 0;
  int ini = Tree[c][ind];
  int x = (l + r) / 2;
  if (Lazy[c][ind] != -1) {
    Tree[c][2 * ind] = min(Lazy[c][ind], x - l + 1);
    Tree[c][2 * ind + 1] = min(Lazy[c][ind], r - x);
    Lazy[c][2 * ind] = Tree[c][2 * ind];
    Lazy[c][2 * ind + 1] = Tree[c][2 * ind + 1];
  }
  Lazy[c][ind] = -1;
  if (l == lx && r == rx) {
    Tree[c][ind] = cnt;
    Lazy[c][ind] = cnt;
  } else if (rx <= x) {
    Tree[c][ind] += update(l, x, lx, rx, cnt, 2 * ind, c);
  } else if (lx > x) {
    Tree[c][ind] += update(x + 1, r, lx, rx, cnt, 2 * ind + 1, c);
  } else {
    Tree[c][ind] += update(l, x, lx, x, min(cnt, x - lx + 1), 2 * ind, c);
    Tree[c][ind] +=
        update(x + 1, r, x + 1, rx, min(cnt, rx - x), 2 * ind + 1, c);
  }
  return Tree[c][ind] - ini;
}
void make(int l, int r, int ind, int c) {
  if (l == r) {
    if (Tree[c][ind]) B[l] = c;
    return;
  }
  int x = (l + r) / 2;
  if (Lazy[c][ind] != -1) {
    Tree[c][2 * ind] = min(Lazy[c][ind], x - l + 1);
    Tree[c][2 * ind + 1] = min(Lazy[c][ind], r - x);
    Lazy[c][2 * ind] = Tree[c][2 * ind];
    Lazy[c][2 * ind + 1] = Tree[c][2 * ind + 1];
  }
  Lazy[c][ind] = -1;
  make(l, x, 2 * ind, c);
  make(x + 1, r, 2 * ind + 1, c);
}
int main() {
  memset(Lazy, -1, sizeof Tree);
  int n = getnum(), q = getnum();
  gets(S + 1);
  for (int i = 1; i <= n; i++) A[i] = S[i] - 'a' + 1;
  for (int i = 1; i <= 26; i++) {
    create(1, n, 1, i);
  }
  for (; q--;) {
    int l = getnum(), r = getnum(), type = getnum(), cnt = 0, sum = 0;
    int temp[30];
    for (int i = 1; i <= 26; i++) temp[i] = get(1, n, l, r, 1, i);
    for (int i = 1; i <= 26; i++) {
      int x = temp[i];
      if (type) {
        update(1, n, l, l + cnt - 1, 0, 1, i);
        update(1, n, l + cnt, l + cnt + x - 1, x, 1, i);
        update(1, n, l + cnt + x, r, 0, 1, i);
      } else {
        update(1, n, l, r - cnt - x, 0, 1, i);
        update(1, n, r - cnt - x + 1, r - cnt, x, 1, i);
        update(1, n, r - cnt + 1, r, 0, 1, i);
      }
      cnt += x;
    }
  }
  for (int i = 1; i <= 26; i++) make(1, n, 1, i);
  for (int i = 1; i <= n; i++) putchar(B[i] + 'a' - 1);
}

### Prompt

Develop a solution in Cpp to the problem described below:

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;
inline long long getnum() {
  char c = getchar();
  long long num, sign = 1;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') sign = -1;
  for (num = 0; c >= '0' && c <= '9';) {
    c -= '0';
    num = num * 10 + c;
    c = getchar();
  }
  return num * sign;
}
char S[100006];
int A[100006], B[100006];
int Tree[30][100006 * 3 * 2];
int Lazy[30][100006 * 3 * 2];
int create(int l, int r, int ind, int c) {
  if (l == r) {
    if (A[l] == c)
      Tree[c][ind] = 1;
    else
      Tree[c][ind] = 0;
    return Tree[c][ind];
  }
  int x = (l + r) / 2;
  Tree[c][ind] = create(l, x, 2 * ind, c) + create(x + 1, r, 2 * ind + 1, c);
  return Tree[c][ind];
}
int get(int l, int r, int lx, int rx, int ind, int c) {
  int x = (l + r) / 2;
  if (Lazy[c][ind] != -1) {
    Tree[c][2 * ind] = min(Lazy[c][ind], x - l + 1);
    Tree[c][2 * ind + 1] = min(Lazy[c][ind], r - x);
    Lazy[c][2 * ind] = Tree[c][2 * ind];
    Lazy[c][2 * ind + 1] = Tree[c][2 * ind + 1];
  }
  Lazy[c][ind] = -1;
  if (l == lx && r == rx) {
    return Tree[c][ind];
  }
  if (rx <= x)
    return get(l, x, lx, rx, 2 * ind, c);
  else if (lx > x)
    return get(x + 1, r, lx, rx, 2 * ind + 1, c);
  else
    return get(l, x, lx, x, 2 * ind, c) +
           get(x + 1, r, x + 1, rx, 2 * ind + 1, c);
}
int update(int l, int r, int lx, int rx, int cnt, int ind, int c) {
  if (lx > rx) return 0;
  int ini = Tree[c][ind];
  int x = (l + r) / 2;
  if (Lazy[c][ind] != -1) {
    Tree[c][2 * ind] = min(Lazy[c][ind], x - l + 1);
    Tree[c][2 * ind + 1] = min(Lazy[c][ind], r - x);
    Lazy[c][2 * ind] = Tree[c][2 * ind];
    Lazy[c][2 * ind + 1] = Tree[c][2 * ind + 1];
  }
  Lazy[c][ind] = -1;
  if (l == lx && r == rx) {
    Tree[c][ind] = cnt;
    Lazy[c][ind] = cnt;
  } else if (rx <= x) {
    Tree[c][ind] += update(l, x, lx, rx, cnt, 2 * ind, c);
  } else if (lx > x) {
    Tree[c][ind] += update(x + 1, r, lx, rx, cnt, 2 * ind + 1, c);
  } else {
    Tree[c][ind] += update(l, x, lx, x, min(cnt, x - lx + 1), 2 * ind, c);
    Tree[c][ind] +=
        update(x + 1, r, x + 1, rx, min(cnt, rx - x), 2 * ind + 1, c);
  }
  return Tree[c][ind] - ini;
}
void make(int l, int r, int ind, int c) {
  if (l == r) {
    if (Tree[c][ind]) B[l] = c;
    return;
  }
  int x = (l + r) / 2;
  if (Lazy[c][ind] != -1) {
    Tree[c][2 * ind] = min(Lazy[c][ind], x - l + 1);
    Tree[c][2 * ind + 1] = min(Lazy[c][ind], r - x);
    Lazy[c][2 * ind] = Tree[c][2 * ind];
    Lazy[c][2 * ind + 1] = Tree[c][2 * ind + 1];
  }
  Lazy[c][ind] = -1;
  make(l, x, 2 * ind, c);
  make(x + 1, r, 2 * ind + 1, c);
}
int main() {
  memset(Lazy, -1, sizeof Tree);
  int n = getnum(), q = getnum();
  gets(S + 1);
  for (int i = 1; i <= n; i++) A[i] = S[i] - 'a' + 1;
  for (int i = 1; i <= 26; i++) {
    create(1, n, 1, i);
  }
  for (; q--;) {
    int l = getnum(), r = getnum(), type = getnum(), cnt = 0, sum = 0;
    int temp[30];
    for (int i = 1; i <= 26; i++) temp[i] = get(1, n, l, r, 1, i);
    for (int i = 1; i <= 26; i++) {
      int x = temp[i];
      if (type) {
        update(1, n, l, l + cnt - 1, 0, 1, i);
        update(1, n, l + cnt, l + cnt + x - 1, x, 1, i);
        update(1, n, l + cnt + x, r, 0, 1, i);
      } else {
        update(1, n, l, r - cnt - x, 0, 1, i);
        update(1, n, r - cnt - x + 1, r - cnt, x, 1, i);
        update(1, n, r - cnt + 1, r, 0, 1, i);
      }
      cnt += x;
    }
  }
  for (int i = 1; i <= 26; i++) make(1, n, 1, i);
  for (int i = 1; i <= n; i++) putchar(B[i] + 'a' - 1);
}

```