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