human
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...
 Write me a Python program to fix of b, but a ≠ b?
assistant
#Here is Python program to fix of b, but a ≠ b.

''' E. Middle Duplication
https://codeforces.com/contest/1623/problem/E
'''

import io, os, sys
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline  # decode().strip() if str
output = sys.stdout.write

DEBUG = os.environ.get('debug') is not None

if DEBUG:
    from inspect import currentframe, getframeinfo
    from re import search

def debug(*args):
    if not DEBUG: return
    frame = currentframe().f_back
    s = getframeinfo(frame).code_context[0]
    r = search(r"\((.*)\)", s).group(1)
    vnames = r.split(', ')
    var_and_vals = [f'{var}={val}' for var, val in zip(vnames, args)]
    prefix = f'{currentframe().f_back.f_lineno:02d}: '
    print(f'{prefix}{", ".join(var_and_vals)}')

INF = float('inf')

# -----------------------------------------

from types import GeneratorType
def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack: return f(*args, **kwargs)
        to = f(*args, **kwargs)
        while True:
            if type(to) is GeneratorType:
                stack.append(to)
                to = next(to)
            else:
                stack.pop()
                if not stack: break
                to = stack[-1].send(to)
        return to
    return wrappedfunc

def main():
    N, K = list(map(int, input().split()))
    S = input().decode().strip()

    L, R = [-1]*N, [-1]*N
    for p in range(N):
        l, r = map(int, input().split())
        L[p], R[p] = l-1, r-1

    # inorder
    inorder = []

    @bootstrap
    def dfs1(u):
        if L[u] > -1: yield dfs1(L[u])
        inorder.append(u)
        if R[u] > -1: yield dfs1(R[u])
        yield None
    dfs1(0)

    # can duplicate if next different node exists and is greater
    good = [False]*N
    last = ''
    for i in range(N-2, -1, -1):
        u, v = inorder[i], inorder[i+1]
        if S[u] != S[v]: last = S[v]
        if S[u] < last: good[u] = True

    # greedily duplicate following inorder 
    # cost = cost if duplicate u; equals distance from u to nearest dup ancestor
    dup = [False]*N

   ...