406825: GYM102566 B BLAT

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. BLATtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard 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.

ExamplesInput
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

加入题单

上一题 下一题 算法标签: