Consider a string s of length n that consists of lowercase Latin alphabetic characters. You are given an array A of size 26 showing the value for each alphabet. You must output the subsequence of size k whose sum of values is maximum.
If there are multiple subsequences available, then print the lexicographically smallest sequence.
String p is lexicographically smaller than string q if p is a prefix of q and is not equal to q or there exists i, such that pi < qi and for all j < i it is satisfied that pj = qj. For example, 'abc' is lexicographically smaller than 'abcd', 'abd' is lexicographically smaller than 'abec', and 'afa' is not lexicographically smaller than 'ab'.
Input format
- The first line contains an integer t representing the number of test cases.
- For each test case, you are given two integers n and k, a string s, and an array A of length 26.
Output format
Print a string for each test case.
Constraints
1≤t≤1e51≤k≤n≤1e50≤A[i]≤1e9 (1≤i≤26)Sum of n over t test cases does not exceed 1e5
In the first test case, optimal way is to include 'a' character twice and 'c' character once, so that the obtained sum (5+5+3=13) is maximum. Only two subsequences ("caa" and "aca") are there with sum 13, but "aca" is lexicographically smaller that "caa".
In the second test case, optimal way is to include 'a' character twice, 'c' character twice and 'b' character once, so that the obtained sum (100+100+80+80+50=410) is maximum. Only two subsequences ("abcac" and "acabc") are there with sum 410, but "abcac" is lexicographically smaller that "acabc".
