#include <bits/stdc++.h>
using namespace std;
int pref[27][100005];
int n, q, k;
string s;
struct node {
  int st, en;
  short int lazy;
  int ct[26];
  node(int a, int b) {
    st = a, en = b;
    lazy = 0;
    for (int i = 0; i < 26; i++) {
      ct[i] = pref[i][b] - pref[i][a - 1];
    }
  }
  void splitasc(int no);
  void splitdesc(int no);
};
node *tree[320005];
int *enode[320005];
void node::splitasc(int no) {
  for (int i = 0; i < 26; i++)
    tree[no * 2]->ct[i] = 0, tree[no * 2 + 1]->ct[i] = 0;
  int rem = (st + en) / 2 - st + 1;
  int i;
  for (i = 0; i < 26 && rem > 0; i++) {
    if (ct[i] <= rem) {
      tree[no * 2]->ct[i] = ct[i];
      rem -= ct[i];
    } else {
      tree[no * 2]->ct[i] = rem;
      tree[no * 2 + 1]->ct[i] = ct[i] - rem;
      rem = 0;
    }
  }
  for (; i < 26; i++) tree[no * 2 + 1]->ct[i] = ct[i];
}
void node::splitdesc(int no) {
  for (int i = 0; i < 26; i++)
    tree[no * 2]->ct[i] = 0, tree[no * 2 + 1]->ct[i] = 0;
  int rem = (st + en) / 2 - st + 1;
  int i;
  for (i = 25; i >= 0 && rem > 0; i--) {
    if (ct[i] <= rem) {
      tree[no * 2]->ct[i] = ct[i];
      rem -= ct[i];
    } else {
      tree[no * 2]->ct[i] = rem;
      tree[no * 2 + 1]->ct[i] = ct[i] - rem;
      rem = 0;
    }
  }
  for (; i >= 0; i--) tree[no * 2 + 1]->ct[i] = ct[i];
}
void build(int no, int a, int b) {
  if (a > b) return;
  tree[no] = new node(a, b);
  enode[no] = new int[26];
  if (a == b) return;
  int mid = (a + b) / 2;
  build(no * 2, a, mid);
  build(no * 2 + 1, mid + 1, b);
}
int *copy26(int *ret, int *a) {
  for (int i = 0; i < 26; i++) ret[i] = a[i];
  return ret;
}
int *query(int no, int a, int b, int i, int j) {
  if (a > b || i > j || a > j || b < i) return NULL;
  if (a < b) {
    if (tree[no]->lazy == 1) {
      tree[no]->splitasc(no);
      tree[no * 2]->lazy = 1;
      tree[no * 2 + 1]->lazy = 1;
    } else if (tree[no]->lazy == -1) {
      tree[no]->splitdesc(no);
      tree[no * 2]->lazy = -1;
      tree[no * 2 + 1]->lazy = -1;
    }
    tree[no]->lazy = 0;
  }
  if (a >= i && b <= j) return copy26(enode[no], tree[no]->ct);
  int mid = (a + b) / 2;
  int *res1 = query(no * 2, a, mid, i, j);
  int *res2 = query(no * 2 + 1, mid + 1, b, i, j);
  if (res1 == NULL) return res2;
  if (res2 == NULL) return res1;
  for (int k = 0; k < 26; k++) res1[k] += res2[k];
  return res1;
}
void splitatpointasc(int *ret1, int *ptr, int rem) {
  int i;
  for (i = 0; i < 26; i++) ret1[i] = 0;
  for (i = 0; i < 26 && rem > 0; i++) {
    if (ptr[i] <= rem) {
      ret1[i] = ptr[i];
      rem -= ptr[i];
      ptr[i] = 0;
    } else {
      ret1[i] = rem;
      ptr[i] = ptr[i] - rem;
      rem = 0;
    }
  }
}
void splitatpointdesc(int *ret1, int *ptr, int rem) {
  int i;
  for (i = 0; i < 26; i++) ret1[i] = 0;
  for (i = 25; i >= 0 && rem > 0; i--) {
    if (ptr[i] <= rem) {
      ret1[i] = ptr[i];
      rem -= ptr[i];
      ptr[i] = 0;
    } else {
      ret1[i] = rem;
      ptr[i] = ptr[i] - rem;
      rem = 0;
    }
  }
}
void update1(int no, int a, int b, int i, int j, int *upd) {
  if (a > b || i > j || a > j || b < i) return;
  if (a != b) {
    if (tree[no]->lazy == 1) {
      tree[no]->splitasc(no);
      tree[no * 2]->lazy = 1;
      tree[no * 2 + 1]->lazy = 1;
    } else if (tree[no]->lazy == -1) {
      tree[no]->splitdesc(no);
      tree[no * 2]->lazy = -1;
      tree[no * 2 + 1]->lazy = -1;
    }
    tree[no]->lazy = 0;
  }
  if (a >= i && b <= j) {
    for (int k = 0; k < 26; k++) tree[no]->ct[k] = upd[k];
    if (a != b) {
      tree[no]->splitasc(no);
      tree[no * 2]->lazy = 1;
      tree[no * 2 + 1]->lazy = 1;
    }
    return;
  }
  int mid = (a + b) / 2;
  if (j <= mid)
    update1(no * 2, a, mid, i, j, upd);
  else if (i > mid)
    update1(no * 2 + 1, mid + 1, b, i, j, upd);
  else {
    splitatpointasc(enode[no], upd, mid - i + 1);
    update1(no * 2, a, mid, i, mid, enode[no]);
    update1(no * 2 + 1, mid + 1, b, mid + 1, j, upd);
  }
  for (int k = 0; k < 26; k++)
    tree[no]->ct[k] = tree[no * 2]->ct[k] + tree[no * 2 + 1]->ct[k];
}
void update2(int no, int a, int b, int i, int j, int *upd) {
  if (a > b || i > j || a > j || b < i) return;
  if (a != b) {
    if (tree[no]->lazy == 1) {
      tree[no]->splitasc(no);
      tree[no * 2]->lazy = 1;
      tree[no * 2 + 1]->lazy = 1;
    } else if (tree[no]->lazy == -1) {
      tree[no]->splitdesc(no);
      tree[no * 2]->lazy = -1;
      tree[no * 2 + 1]->lazy = -1;
    }
    tree[no]->lazy = 0;
  }
  if (a >= i && b <= j) {
    for (int k = 0; k < 26; k++) tree[no]->ct[k] = upd[k];
    if (a != b) {
      tree[no]->splitdesc(no);
      tree[no * 2]->lazy = -1;
      tree[no * 2 + 1]->lazy = -1;
    }
    return;
  }
  int mid = (a + b) / 2;
  if (j <= mid)
    update2(no * 2, a, mid, i, j, upd);
  else if (i > mid)
    update2(no * 2 + 1, mid + 1, b, i, j, upd);
  else {
    splitatpointdesc(enode[no], upd, mid - i + 1);
    update2(no * 2, a, mid, i, mid, enode[no]);
    update2(no * 2 + 1, mid + 1, b, mid + 1, j, upd);
  }
  for (int k = 0; k < 26; k++)
    tree[no]->ct[k] = tree[no * 2]->ct[k] + tree[no * 2 + 1]->ct[k];
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> q >> s;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < 26; j++) pref[j][i] = pref[j][i - 1];
    pref[s[i - 1] - 'a'][i]++;
  }
  build(1, 1, n);
  while (q--) {
    int l, r, dir;
    cin >> l >> r >> dir;
    int *ptr = query(1, 1, n, l, r);
    if (dir == 1)
      update1(1, 1, n, l, r, ptr);
    else
      update2(1, 1, n, l, r, ptr);
  }
  for (int i = 1; i <= n; i++) {
    int *curr = query(1, 1, n, i, i);
    for (int j = 0; j < 26; j++) {
      if (curr[j]) {
        cout << ((char)(j + 'a'));
        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;
int pref[27][100005];
int n, q, k;
string s;
struct node {
  int st, en;
  short int lazy;
  int ct[26];
  node(int a, int b) {
    st = a, en = b;
    lazy = 0;
    for (int i = 0; i < 26; i++) {
      ct[i] = pref[i][b] - pref[i][a - 1];
    }
  }
  void splitasc(int no);
  void splitdesc(int no);
};
node *tree[320005];
int *enode[320005];
void node::splitasc(int no) {
  for (int i = 0; i < 26; i++)
    tree[no * 2]->ct[i] = 0, tree[no * 2 + 1]->ct[i] = 0;
  int rem = (st + en) / 2 - st + 1;
  int i;
  for (i = 0; i < 26 && rem > 0; i++) {
    if (ct[i] <= rem) {
      tree[no * 2]->ct[i] = ct[i];
      rem -= ct[i];
    } else {
      tree[no * 2]->ct[i] = rem;
      tree[no * 2 + 1]->ct[i] = ct[i] - rem;
      rem = 0;
    }
  }
  for (; i < 26; i++) tree[no * 2 + 1]->ct[i] = ct[i];
}
void node::splitdesc(int no) {
  for (int i = 0; i < 26; i++)
    tree[no * 2]->ct[i] = 0, tree[no * 2 + 1]->ct[i] = 0;
  int rem = (st + en) / 2 - st + 1;
  int i;
  for (i = 25; i >= 0 && rem > 0; i--) {
    if (ct[i] <= rem) {
      tree[no * 2]->ct[i] = ct[i];
      rem -= ct[i];
    } else {
      tree[no * 2]->ct[i] = rem;
      tree[no * 2 + 1]->ct[i] = ct[i] - rem;
      rem = 0;
    }
  }
  for (; i >= 0; i--) tree[no * 2 + 1]->ct[i] = ct[i];
}
void build(int no, int a, int b) {
  if (a > b) return;
  tree[no] = new node(a, b);
  enode[no] = new int[26];
  if (a == b) return;
  int mid = (a + b) / 2;
  build(no * 2, a, mid);
  build(no * 2 + 1, mid + 1, b);
}
int *copy26(int *ret, int *a) {
  for (int i = 0; i < 26; i++) ret[i] = a[i];
  return ret;
}
int *query(int no, int a, int b, int i, int j) {
  if (a > b || i > j || a > j || b < i) return NULL;
  if (a < b) {
    if (tree[no]->lazy == 1) {
      tree[no]->splitasc(no);
      tree[no * 2]->lazy = 1;
      tree[no * 2 + 1]->lazy = 1;
    } else if (tree[no]->lazy == -1) {
      tree[no]->splitdesc(no);
      tree[no * 2]->lazy = -1;
      tree[no * 2 + 1]->lazy = -1;
    }
    tree[no]->lazy = 0;
  }
  if (a >= i && b <= j) return copy26(enode[no], tree[no]->ct);
  int mid = (a + b) / 2;
  int *res1 = query(no * 2, a, mid, i, j);
  int *res2 = query(no * 2 + 1, mid + 1, b, i, j);
  if (res1 == NULL) return res2;
  if (res2 == NULL) return res1;
  for (int k = 0; k < 26; k++) res1[k] += res2[k];
  return res1;
}
void splitatpointasc(int *ret1, int *ptr, int rem) {
  int i;
  for (i = 0; i < 26; i++) ret1[i] = 0;
  for (i = 0; i < 26 && rem > 0; i++) {
    if (ptr[i] <= rem) {
      ret1[i] = ptr[i];
      rem -= ptr[i];
      ptr[i] = 0;
    } else {
      ret1[i] = rem;
      ptr[i] = ptr[i] - rem;
      rem = 0;
    }
  }
}
void splitatpointdesc(int *ret1, int *ptr, int rem) {
  int i;
  for (i = 0; i < 26; i++) ret1[i] = 0;
  for (i = 25; i >= 0 && rem > 0; i--) {
    if (ptr[i] <= rem) {
      ret1[i] = ptr[i];
      rem -= ptr[i];
      ptr[i] = 0;
    } else {
      ret1[i] = rem;
      ptr[i] = ptr[i] - rem;
      rem = 0;
    }
  }
}
void update1(int no, int a, int b, int i, int j, int *upd) {
  if (a > b || i > j || a > j || b < i) return;
  if (a != b) {
    if (tree[no]->lazy == 1) {
      tree[no]->splitasc(no);
      tree[no * 2]->lazy = 1;
      tree[no * 2 + 1]->lazy = 1;
    } else if (tree[no]->lazy == -1) {
      tree[no]->splitdesc(no);
      tree[no * 2]->lazy = -1;
      tree[no * 2 + 1]->lazy = -1;
    }
    tree[no]->lazy = 0;
  }
  if (a >= i && b <= j) {
    for (int k = 0; k < 26; k++) tree[no]->ct[k] = upd[k];
    if (a != b) {
      tree[no]->splitasc(no);
      tree[no * 2]->lazy = 1;
      tree[no * 2 + 1]->lazy = 1;
    }
    return;
  }
  int mid = (a + b) / 2;
  if (j <= mid)
    update1(no * 2, a, mid, i, j, upd);
  else if (i > mid)
    update1(no * 2 + 1, mid + 1, b, i, j, upd);
  else {
    splitatpointasc(enode[no], upd, mid - i + 1);
    update1(no * 2, a, mid, i, mid, enode[no]);
    update1(no * 2 + 1, mid + 1, b, mid + 1, j, upd);
  }
  for (int k = 0; k < 26; k++)
    tree[no]->ct[k] = tree[no * 2]->ct[k] + tree[no * 2 + 1]->ct[k];
}
void update2(int no, int a, int b, int i, int j, int *upd) {
  if (a > b || i > j || a > j || b < i) return;
  if (a != b) {
    if (tree[no]->lazy == 1) {
      tree[no]->splitasc(no);
      tree[no * 2]->lazy = 1;
      tree[no * 2 + 1]->lazy = 1;
    } else if (tree[no]->lazy == -1) {
      tree[no]->splitdesc(no);
      tree[no * 2]->lazy = -1;
      tree[no * 2 + 1]->lazy = -1;
    }
    tree[no]->lazy = 0;
  }
  if (a >= i && b <= j) {
    for (int k = 0; k < 26; k++) tree[no]->ct[k] = upd[k];
    if (a != b) {
      tree[no]->splitdesc(no);
      tree[no * 2]->lazy = -1;
      tree[no * 2 + 1]->lazy = -1;
    }
    return;
  }
  int mid = (a + b) / 2;
  if (j <= mid)
    update2(no * 2, a, mid, i, j, upd);
  else if (i > mid)
    update2(no * 2 + 1, mid + 1, b, i, j, upd);
  else {
    splitatpointdesc(enode[no], upd, mid - i + 1);
    update2(no * 2, a, mid, i, mid, enode[no]);
    update2(no * 2 + 1, mid + 1, b, mid + 1, j, upd);
  }
  for (int k = 0; k < 26; k++)
    tree[no]->ct[k] = tree[no * 2]->ct[k] + tree[no * 2 + 1]->ct[k];
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> q >> s;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < 26; j++) pref[j][i] = pref[j][i - 1];
    pref[s[i - 1] - 'a'][i]++;
  }
  build(1, 1, n);
  while (q--) {
    int l, r, dir;
    cin >> l >> r >> dir;
    int *ptr = query(1, 1, n, l, r);
    if (dir == 1)
      update1(1, 1, n, l, r, ptr);
    else
      update2(1, 1, n, l, r, ptr);
  }
  for (int i = 1; i <= n; i++) {
    int *curr = query(1, 1, n, i, i);
    for (int j = 0; j < 26; j++) {
      if (curr[j]) {
        cout << ((char)(j + 'a'));
        break;
      }
    }
  }
  return 0;
}

```