#include <bits/stdc++.h>
using namespace std;
template <typename T>
void Read(T &x) {
  char ch;
  bool neg = 0;
  x = 0;
  while (!isdigit(ch = getchar()) && ch != '-')
    ;
  if (ch == '-') {
    neg = 1;
    ch = getchar();
  }
  do {
    x = x * 10 + ch - 48;
  } while (isdigit(ch = getchar()));
  if (neg) x = -x;
  return;
}
template <typename T>
void Write(T x) {
  char ch[32];
  int cnt = 0;
  bool neg = 0;
  if (x < 0) {
    neg = 1;
    x = -x;
  }
  do {
    ch[++cnt] = x % 10 + 48;
    x /= 10;
  } while (x);
  if (neg) putchar('-');
  for (int i = (cnt); i >= (1); --i) putchar(ch[i]);
}
template <typename T>
void Writeln(T x) {
  Write(x);
  putchar('\n');
}
template <typename T>
void Writesp(T x) {
  Write(x);
  putchar(' ');
}
const int MAX = 1e5 + 1;
const int MAXIT = 26;
int n, q;
struct Segment {
  pair<int, int> Tree[MAX << 2];
  void down(int id) {
    if (Tree[id].second == -1) return;
    int t = Tree[id].second;
    int mid = (Tree[id].second + 1) / 2;
    Tree[2 * id].first = mid;
    Tree[2 * id].second = mid;
    Tree[2 * id + 1].first = t - mid;
    Tree[2 * id + 1].second = t - mid;
    Tree[id].second = -1;
  }
  void Update(int id, int l, int r, int u, int v, int val) {
    if (l > v || r < u) return;
    if (l >= u && r <= v) {
      if (val == 0)
        Tree[id] = pair<int, int>(0, 0);
      else
        Tree[id] = pair<int, int>(r - l + 1, r - l + 1);
      return;
    }
    down(id);
    int mid = (l + r) >> 1;
    Update(2 * id, l, mid, u, v, val);
    Update(2 * id + 1, mid + 1, r, u, v, val);
    Tree[id].first = Tree[2 * id].first + Tree[2 * id + 1].first;
  }
  int Query(int id, int l, int r, int u, int v) {
    if (l > v || r < u) return 0;
    if (l >= u && r <= v) return Tree[id].first;
    down(id);
    int mid = (l + r) >> 1;
    int L = Query(2 * id, l, mid, u, v);
    int R = Query(2 * id + 1, mid + 1, r, u, v);
    return L + R;
  }
} IT[MAXIT];
int main(int argc, char const *argv[]) {
  Read(n);
  Read(q);
  for (int i = (0); i <= (25); ++i)
    for (int j = (1); j <= (n << 2); ++j) IT[i].Tree[j] = pair<int, int>(0, -1);
  for (int i = (1); i <= (n); ++i) {
    char ch;
    do {
      ch = getchar();
    } while (!isalpha(ch));
    IT[ch - 97].Update(1, 1, n, i, i, 1);
  }
  int u, v, c, index;
  int num[MAXIT];
  for (int i = (1); i <= (q); ++i) {
    memset(num, 0, sizeof num);
    Read(u);
    Read(v);
    Read(c);
    for (int j = (0); j < (26); ++j) {
      int tmp = IT[j].Query(1, 1, n, u, v);
      if (!tmp) continue;
      num[j] = tmp;
      IT[j].Update(1, 1, n, u, v, 0);
    }
    if (c) {
      index = u;
      for (int j = (0); j < (26); ++j)
        if (num[j]) {
          IT[j].Update(1, 1, n, index, index + num[j] - 1, num[j]);
          index += num[j];
        }
    } else {
      index = u;
      for (int j = (25); j >= (0); --j)
        if (num[j]) {
          IT[j].Update(1, 1, n, index, index + num[j] - 1, num[j]);
          index += num[j];
        }
    }
  }
  for (int i = (1); i <= (n); ++i)
    for (int j = (0); j < (26); ++j)
      if (IT[j].Query(1, 1, n, i, i)) {
        putchar(j + 97);
        break;
      }
  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>
void Read(T &x) {
  char ch;
  bool neg = 0;
  x = 0;
  while (!isdigit(ch = getchar()) && ch != '-')
    ;
  if (ch == '-') {
    neg = 1;
    ch = getchar();
  }
  do {
    x = x * 10 + ch - 48;
  } while (isdigit(ch = getchar()));
  if (neg) x = -x;
  return;
}
template <typename T>
void Write(T x) {
  char ch[32];
  int cnt = 0;
  bool neg = 0;
  if (x < 0) {
    neg = 1;
    x = -x;
  }
  do {
    ch[++cnt] = x % 10 + 48;
    x /= 10;
  } while (x);
  if (neg) putchar('-');
  for (int i = (cnt); i >= (1); --i) putchar(ch[i]);
}
template <typename T>
void Writeln(T x) {
  Write(x);
  putchar('\n');
}
template <typename T>
void Writesp(T x) {
  Write(x);
  putchar(' ');
}
const int MAX = 1e5 + 1;
const int MAXIT = 26;
int n, q;
struct Segment {
  pair<int, int> Tree[MAX << 2];
  void down(int id) {
    if (Tree[id].second == -1) return;
    int t = Tree[id].second;
    int mid = (Tree[id].second + 1) / 2;
    Tree[2 * id].first = mid;
    Tree[2 * id].second = mid;
    Tree[2 * id + 1].first = t - mid;
    Tree[2 * id + 1].second = t - mid;
    Tree[id].second = -1;
  }
  void Update(int id, int l, int r, int u, int v, int val) {
    if (l > v || r < u) return;
    if (l >= u && r <= v) {
      if (val == 0)
        Tree[id] = pair<int, int>(0, 0);
      else
        Tree[id] = pair<int, int>(r - l + 1, r - l + 1);
      return;
    }
    down(id);
    int mid = (l + r) >> 1;
    Update(2 * id, l, mid, u, v, val);
    Update(2 * id + 1, mid + 1, r, u, v, val);
    Tree[id].first = Tree[2 * id].first + Tree[2 * id + 1].first;
  }
  int Query(int id, int l, int r, int u, int v) {
    if (l > v || r < u) return 0;
    if (l >= u && r <= v) return Tree[id].first;
    down(id);
    int mid = (l + r) >> 1;
    int L = Query(2 * id, l, mid, u, v);
    int R = Query(2 * id + 1, mid + 1, r, u, v);
    return L + R;
  }
} IT[MAXIT];
int main(int argc, char const *argv[]) {
  Read(n);
  Read(q);
  for (int i = (0); i <= (25); ++i)
    for (int j = (1); j <= (n << 2); ++j) IT[i].Tree[j] = pair<int, int>(0, -1);
  for (int i = (1); i <= (n); ++i) {
    char ch;
    do {
      ch = getchar();
    } while (!isalpha(ch));
    IT[ch - 97].Update(1, 1, n, i, i, 1);
  }
  int u, v, c, index;
  int num[MAXIT];
  for (int i = (1); i <= (q); ++i) {
    memset(num, 0, sizeof num);
    Read(u);
    Read(v);
    Read(c);
    for (int j = (0); j < (26); ++j) {
      int tmp = IT[j].Query(1, 1, n, u, v);
      if (!tmp) continue;
      num[j] = tmp;
      IT[j].Update(1, 1, n, u, v, 0);
    }
    if (c) {
      index = u;
      for (int j = (0); j < (26); ++j)
        if (num[j]) {
          IT[j].Update(1, 1, n, index, index + num[j] - 1, num[j]);
          index += num[j];
        }
    } else {
      index = u;
      for (int j = (25); j >= (0); --j)
        if (num[j]) {
          IT[j].Update(1, 1, n, index, index + num[j] - 1, num[j]);
          index += num[j];
        }
    }
  }
  for (int i = (1); i <= (n); ++i)
    for (int j = (0); j < (26); ++j)
      if (IT[j].Query(1, 1, n, i, i)) {
        putchar(j + 97);
        break;
      }
  return 0;
}

```