B. BLAT
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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$$$.

Output

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

Examples
Input
6 6
a b a a a a
1 2
2 3
2 5
2 6
3 4
Output
aa
Input
6 8
a b a a a a
1 2
2 3
2 5
2 6
3 4
Output
aab