#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
constexpr long long mod = 1000000007;
const long long INF = mod * mod;
template <typename T>
void chmin(T& a, T b) {
  a = min(a, b);
}
template <typename T>
void chmax(T& a, T b) {
  a = max(a, b);
}
template <typename T>
void cinarray(vector<T>& v) {
  for (int i = 0; i < v.size(); i++) cin >> v[i];
}
template <typename T>
void coutarray(vector<T>& v) {
  for (int i = 0; i < v.size(); i++) {
    if (i > 0) cout << " ";
    cout << v[i];
  }
  cout << "\n";
}
long long mod_pow(long long x, long long n, long long m = mod) {
  if (n < 0) {
    long long res = mod_pow(x, -n, m);
    return mod_pow(res, m - 2, m);
  }
  if (abs(x) >= m) x %= m;
  if (x < 0) x += m;
  if (x == 0) return 0;
  long long res = 1;
  while (n) {
    if (n & 1) res = res * x % m;
    x = x * x % m;
    n >>= 1;
  }
  return res;
}
struct modint {
  int n;
  modint() : n(0) { ; }
  modint(long long m) {
    if (m < 0 || mod <= m) {
      m %= mod;
      if (m < 0) m += mod;
    }
    n = m;
  }
  operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint& a, modint b) {
  a.n += b.n;
  if (a.n >= mod) a.n -= mod;
  return a;
}
modint operator-=(modint& a, modint b) {
  a.n -= b.n;
  if (a.n < 0) a.n += mod;
  return a;
}
modint operator*=(modint& a, modint b) {
  a.n = ((long long)a.n * b.n) % mod;
  return a;
}
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, long long n) {
  if (n == 0) return modint(1);
  modint res = (a * a) ^ (n / 2);
  if (n % 2) res = res * a;
  return res;
}
long long inv(long long a, long long p) {
  return (a == 1 ? 1 : (1 - p * inv(p % a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }
modint operator/=(modint& a, modint b) {
  a = a / b;
  return a;
}
const int max_n = 1 << 10;
modint fact[max_n], factinv[max_n];
void init_f() {
  fact[0] = modint(1);
  for (int i = 0; i < max_n - 1; i++) {
    fact[i + 1] = fact[i] * modint(i + 1);
  }
  factinv[max_n - 1] = modint(1) / fact[max_n - 1];
  for (int i = max_n - 2; i >= 0; i--) {
    factinv[i] = factinv[i + 1] * modint(i + 1);
  }
}
modint comb(int a, int b) {
  if (a < 0 || b < 0 || a < b) return 0;
  return fact[a] * factinv[b] * factinv[a - b];
}
modint combP(int a, int b) {
  if (a < 0 || b < 0 || a < b) return 0;
  return fact[a] * factinv[a - b];
}
long long gcd(long long a, long long b) {
  a = abs(a);
  b = abs(b);
  if (a < b) swap(a, b);
  while (b) {
    long long r = a % b;
    a = b;
    b = r;
  }
  return a;
}
const long double eps = 1e-8;
const long double pi = acosl(-1.0);
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
using mP = pair<modint, modint>;
int par[1 << 18][18];
void solve() {
  int n, k;
  cin >> n >> k;
  string s;
  cin >> s;
  vector<int> l(n), r(n);
  par[0][0] = -1;
  for (int i = 0; i < n; i++) {
    cin >> l[i] >> r[i];
    l[i]--;
    r[i]--;
    if (l[i] >= 0) par[l[i]][0] = i;
    if (r[i] >= 0) par[r[i]][0] = i;
  }
  for (int j = 0; j < 17; j++) {
    for (int i = 0; i < n; i++) {
      if (par[i][j] < 0)
        par[i][j + 1] = -1;
      else
        par[i][j + 1] = par[par[i][j]][j];
    }
  }
  vector<int> ids;
  function<void(int)> dfs = [&](int id) {
    if (l[id] >= 0) dfs(l[id]);
    ids.push_back(id);
    if (r[id] >= 0) dfs(r[id]);
  };
  dfs(0);
  vector<bool> b(n);
  for (int i = 0; i < n; i++) {
    int le = i;
    while (i + 1 < n && s[ids[i]] == s[ids[i + 1]]) i++;
    if (i + 1 == n || s[ids[i + 1]] < s[ids[i]]) {
      for (int j = le; j <= i; j++) b[ids[j]] = true;
    }
  }
  vector<bool> used(n);
  string ans;
  function<void(int)> dfs3 = [&](int id) {
    if (l[id] >= 0) dfs3(l[id]);
    ans.push_back(s[id]);
    if (r[id] >= 0) dfs3(r[id]);
  };
  function<void(int)> dfs2 = [&](int id) {
    if (l[id] >= 0) dfs2(l[id]);
    if (!used[id]) {
      if (!b[id]) {
        int cur = id;
        int ad = 1;
        for (int j = 18 - 1; j >= 0; j--) {
          int p = par[cur][j];
          if (p >= 0 && !used[p]) {
            ad += (1 << j);
            cur = p;
          }
        }
        if (ad <= k) {
          k -= ad;
          cur = id;
          while (cur >= 0 && !used[cur]) {
            used[cur] = true;
            cur = par[cur][0];
          }
        }
      }
    }
    if (used[id]) {
      ans.push_back(s[id]);
      ans.push_back(s[id]);
      if (r[id] >= 0) dfs2(r[id]);
    } else {
      ans.push_back(s[id]);
      if (r[id] >= 0) dfs3(r[id]);
    }
  };
  dfs2(0);
  cout << ans << "\n";
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(10);
  solve();
  return 0;
}

### Prompt

Develop a solution in Cpp to the problem described below:

A binary tree of n nodes is given. Nodes of the tree are numbered from 1 to n and the root is the node 1. Each node can have no child, only one left child, only one right child, or both children. For convenience, let's denote l_u and r_u as the left and the right child of the node u respectively, l_u = 0 if u does not have the left child, and r_u = 0 if the node u does not have the right child.

Each node has a string label, initially is a single character c_u. Let's define the string representation of the binary tree as the concatenation of the labels of the nodes in the in-order. Formally, let f(u) be the string representation of the tree rooted at the node u. f(u) is defined as follows: $$$ f(u) = \begin{cases} <empty string>, & if u = 0; \\\ f(l_u) + c_u + f(r_u) & otherwise, \end{cases}  where +$$$ denotes the string concatenation operation.

This way, the string representation of the tree is f(1).

For each node, we can duplicate its label at most once, that is, assign c_u with c_u + c_u, but only if u is the root of the tree, or if its parent also has its label duplicated.

You are given the tree and an integer k. What is the lexicographically smallest string representation of the tree, if we can duplicate labels of at most k nodes?

A string a is lexicographically smaller than a string b if and only if one of the following holds: 

  * a is a prefix of b, but a ≠ b; 
  * in the first position where a and b differ, the string a has a letter that appears earlier in the alphabet than the corresponding letter in b. 

Input

The first line contains two integers n and k (1 ≤ k ≤ n ≤ 2 ⋅ 10^5).

The second line contains a string c of n lower-case English letters, where c_i is the initial label of the node i for 1 ≤ i ≤ n. Note that the given string c is not the initial string representation of the tree.

The i-th of the next n lines contains two integers l_i and r_i (0 ≤ l_i, r_i ≤ n). If the node i does not have the left child, l_i = 0, and if the node i does not have the right child, r_i = 0.

It is guaranteed that the given input forms a binary tree, rooted at 1.

Output

Print a single line, containing the lexicographically smallest string representation of the tree if at most k nodes have their labels duplicated.

Examples

Input


4 3
abab
2 3
0 0
0 4
0 0


Output


baaaab

Input


8 2
kadracyn
2 5
3 4
0 0
0 0
6 8
0 7
0 0
0 0


Output


daarkkcyan

Input


8 3
kdaracyn
2 5
0 3
0 4
0 0
6 8
0 7
0 0
0 0


Output


darkcyan

Note

The images below present the tree for the examples. The number in each node is the node number, while the subscripted letter is its label. To the right is the string representation of the tree, with each letter having the same color as the corresponding node.

Here is the tree for the first example. Here we duplicated the labels of nodes 1 and 3. We should not duplicate the label of node 2 because it would give us the string "bbaaab", which is lexicographically greater than "baaaab".

<image>

In the second example, we can duplicate the labels of nodes 1 and 2. Note that only duplicating the label of the root will produce a worse result than the initial string.

<image>

In the third example, we should not duplicate any character at all. Even though we would want to duplicate the label of the node 3, by duplicating it we must also duplicate the label of the node 2, which produces a worse result.

<image>

There is no way to produce string "darkkcyan" from a tree with the initial string representation "darkcyan" :(.

### Response

```cpp
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
constexpr long long mod = 1000000007;
const long long INF = mod * mod;
template <typename T>
void chmin(T& a, T b) {
  a = min(a, b);
}
template <typename T>
void chmax(T& a, T b) {
  a = max(a, b);
}
template <typename T>
void cinarray(vector<T>& v) {
  for (int i = 0; i < v.size(); i++) cin >> v[i];
}
template <typename T>
void coutarray(vector<T>& v) {
  for (int i = 0; i < v.size(); i++) {
    if (i > 0) cout << " ";
    cout << v[i];
  }
  cout << "\n";
}
long long mod_pow(long long x, long long n, long long m = mod) {
  if (n < 0) {
    long long res = mod_pow(x, -n, m);
    return mod_pow(res, m - 2, m);
  }
  if (abs(x) >= m) x %= m;
  if (x < 0) x += m;
  if (x == 0) return 0;
  long long res = 1;
  while (n) {
    if (n & 1) res = res * x % m;
    x = x * x % m;
    n >>= 1;
  }
  return res;
}
struct modint {
  int n;
  modint() : n(0) { ; }
  modint(long long m) {
    if (m < 0 || mod <= m) {
      m %= mod;
      if (m < 0) m += mod;
    }
    n = m;
  }
  operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint& a, modint b) {
  a.n += b.n;
  if (a.n >= mod) a.n -= mod;
  return a;
}
modint operator-=(modint& a, modint b) {
  a.n -= b.n;
  if (a.n < 0) a.n += mod;
  return a;
}
modint operator*=(modint& a, modint b) {
  a.n = ((long long)a.n * b.n) % mod;
  return a;
}
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, long long n) {
  if (n == 0) return modint(1);
  modint res = (a * a) ^ (n / 2);
  if (n % 2) res = res * a;
  return res;
}
long long inv(long long a, long long p) {
  return (a == 1 ? 1 : (1 - p * inv(p % a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }
modint operator/=(modint& a, modint b) {
  a = a / b;
  return a;
}
const int max_n = 1 << 10;
modint fact[max_n], factinv[max_n];
void init_f() {
  fact[0] = modint(1);
  for (int i = 0; i < max_n - 1; i++) {
    fact[i + 1] = fact[i] * modint(i + 1);
  }
  factinv[max_n - 1] = modint(1) / fact[max_n - 1];
  for (int i = max_n - 2; i >= 0; i--) {
    factinv[i] = factinv[i + 1] * modint(i + 1);
  }
}
modint comb(int a, int b) {
  if (a < 0 || b < 0 || a < b) return 0;
  return fact[a] * factinv[b] * factinv[a - b];
}
modint combP(int a, int b) {
  if (a < 0 || b < 0 || a < b) return 0;
  return fact[a] * factinv[a - b];
}
long long gcd(long long a, long long b) {
  a = abs(a);
  b = abs(b);
  if (a < b) swap(a, b);
  while (b) {
    long long r = a % b;
    a = b;
    b = r;
  }
  return a;
}
const long double eps = 1e-8;
const long double pi = acosl(-1.0);
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
using mP = pair<modint, modint>;
int par[1 << 18][18];
void solve() {
  int n, k;
  cin >> n >> k;
  string s;
  cin >> s;
  vector<int> l(n), r(n);
  par[0][0] = -1;
  for (int i = 0; i < n; i++) {
    cin >> l[i] >> r[i];
    l[i]--;
    r[i]--;
    if (l[i] >= 0) par[l[i]][0] = i;
    if (r[i] >= 0) par[r[i]][0] = i;
  }
  for (int j = 0; j < 17; j++) {
    for (int i = 0; i < n; i++) {
      if (par[i][j] < 0)
        par[i][j + 1] = -1;
      else
        par[i][j + 1] = par[par[i][j]][j];
    }
  }
  vector<int> ids;
  function<void(int)> dfs = [&](int id) {
    if (l[id] >= 0) dfs(l[id]);
    ids.push_back(id);
    if (r[id] >= 0) dfs(r[id]);
  };
  dfs(0);
  vector<bool> b(n);
  for (int i = 0; i < n; i++) {
    int le = i;
    while (i + 1 < n && s[ids[i]] == s[ids[i + 1]]) i++;
    if (i + 1 == n || s[ids[i + 1]] < s[ids[i]]) {
      for (int j = le; j <= i; j++) b[ids[j]] = true;
    }
  }
  vector<bool> used(n);
  string ans;
  function<void(int)> dfs3 = [&](int id) {
    if (l[id] >= 0) dfs3(l[id]);
    ans.push_back(s[id]);
    if (r[id] >= 0) dfs3(r[id]);
  };
  function<void(int)> dfs2 = [&](int id) {
    if (l[id] >= 0) dfs2(l[id]);
    if (!used[id]) {
      if (!b[id]) {
        int cur = id;
        int ad = 1;
        for (int j = 18 - 1; j >= 0; j--) {
          int p = par[cur][j];
          if (p >= 0 && !used[p]) {
            ad += (1 << j);
            cur = p;
          }
        }
        if (ad <= k) {
          k -= ad;
          cur = id;
          while (cur >= 0 && !used[cur]) {
            used[cur] = true;
            cur = par[cur][0];
          }
        }
      }
    }
    if (used[id]) {
      ans.push_back(s[id]);
      ans.push_back(s[id]);
      if (r[id] >= 0) dfs2(r[id]);
    } else {
      ans.push_back(s[id]);
      if (r[id] >= 0) dfs3(r[id]);
    }
  };
  dfs2(0);
  cout << ans << "\n";
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(10);
  solve();
  return 0;
}

```