Task On The Board

2000ms

262144K

Description:

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.

Input:

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:

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.

Sample Input:

4
abac
3
2 1 0
abc
1
0
abba
3
1 0 1
ecoosdcefr
10
38 13 24 14 11 5 3 24 17 0

Sample Output:

aac
b
aba
codeforces

Note:

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.

Informação

Provedor Codeforces

Código CF1367D