Task On The Board
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.
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.
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.
Samples
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
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.