CF1367D Task On The Board

Polycarp wrote on the board a string $ s $ containing only lowercase Latin letters ('a'-'z'). This string is known for you and given in the input. After that, he erased some letters from the string $ s $ , and he rewrote the remaining letters in any order. As a result, he got some new string $ t $ . You have to find it with some additional information. Suppose that the string $ t $ has length $ m $ and the characters are numbered from left to right from $ 1 $ to $ m $ . You are given a sequence of $ m $ integers: $ b_1, b_2, \ldots, b_m $ , where $ b_i $ is the sum of the distances $ |i-j| $ from the index $ i $ to all such indices $ j $ that $ t_j > t_i $ (consider that 'a'<'b'<...<'z'). In other words, to calculate $ b_i $ , Polycarp finds all such indices $ j $ that the index $ j $ contains a letter that is later in the alphabet than $ t_i $ and sums all the values $ |i-j| $ . For example, if $ t $ = "abzb", then: - since $ t_1 $ ='a', all other indices contain letters which are later in the alphabet, that is: $ b_1=|1-2|+|1-3|+|1-4|=1+2+3=6 $ ; - since $ t_2 $ ='b', only the index $ j=3 $ contains the letter, which is later in the alphabet, that is: $ b_2=|2-3|=1 $ ; - since $ t_3 $ ='z', then there are no indexes $ j $ such that $ t_j>t_i $ , thus $ b_3=0 $ ; - since $ t_4 $ ='b', only the index $ j=3 $ contains the letter, which is later in the alphabet, that is: $ b_4=|4-3|=1 $ . Thus, if $ t $ = "abzb", then $ b=[6,1,0,1] $ . Given the string $ s $ and the array $ b $ , find any possible string $ t $ for which the following two requirements are fulfilled simultaneously: - $ t $ is obtained from $ s $ by erasing some letters (possibly zero) and then writing the rest in any order; - the array, constructed from the string $ t $ according to the rules above, equals to the array $ b $ specified in the input data.

The first line contains an integer $ q $ ( $ 1 \le q \le 100 $ ) — the number of test cases in the test. Then $ q $ test cases follow. Each test case consists of three lines: - the first line contains string $ s $ , which has a length from $ 1 $ to $ 50 $ and consists of lowercase English letters; - the second line contains positive integer $ m $ ( $ 1 \le m \le |s| $ ), where $ |s| $ is the length of the string $ s $ , and $ m $ is the length of the array $ b $ ; - the third line contains the integers $ b_1, b_2, \dots, b_m $ ( $ 0 \le b_i \le 1225 $ ). It is guaranteed that in each test case an answer exists.

Output $ q $ lines: the $ k $ -th of them should contain the answer (string $ t $ ) to the $ k $ -th test case. It is guaranteed that an answer to each test case exists. If there are several answers, output any.

In the first test case, such strings $ t $ are suitable: "aac', "aab". In the second test case, such trings $ t $ are suitable: "a", "b", "c". In the third test case, only the string $ t $ equals to "aba" is suitable, but the character 'b' can be from the second or third position.