406825: GYM102566 B BLAT

Inspired by the ingenious encryption techniques of messages used during wars, the AGM team decided to form its own method and named it "Beautiful Lexicographical Alphabetical Trees" or BLAT for short.

We give you a tree with $$$N$$$ ($$$1 \leq N \leq 100.000$$$) nodes, each having a letter assigned to them. The path from node $$$A$$$ to node $$$B$$$ is represented by the succession of letters of the nodes you pass through along the path, including the ones of $$$A$$$ and $$$B$$$. Be careful, the path from $$$A$$$ to $$$B$$$ may be different from the path from $$$B$$$ to $$$A$$$, so they are considered separate paths. Of course, the AGM team didn't want you to find the decryption too boring, so you receive a number $$$K$$$ ($$$1 \leq K \leq min(N^2, 100.000)$$$) as well. Our message is represented by the $$$K$$$th lexicographical smallest path, considering all of them. Decrypt it and you will be rewarded.

The first line of the input will contain three positive integers $$$N,\ K$$$ that represent the number of nodes and the number received from the AGM team.

The next line will contain $$$N$$$ lowercase letters $$$l_1,l_2,l_3,...,l_n$$$, where $$$l_i$$$ represents the letter corresponding to the $$$i$$$th node.

The last $$$N-1$$$ lines will contain three positive integers $$$a,\ b$$$ that represent that there exists a bidirectional road between nodes $$$a$$$ and $$$b$$$.

The output should contain a string of lowercase letters representing the decrypted message.

6 6
a b a a a a
1 2
2 3
2 5
2 6
3 4

aa

6 8
a b a a a a
1 2
2 3
2 5
2 6
3 4

aab