1367D · Task On The Board

Problem: 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 Format: 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 Format: 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.

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.