Task On The Board
Contest: Codeforces Round 650 (Div. 3)
Difficulty rating: 1800
Tags: constructive algorithms, greedy, implementation, sortings

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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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.

Example 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

Example output:
aac
b
aba
codeforces

Editorial:
We will construct the string $$$t$$$, starting with the largest letters. Note that if $$$b_i = 0$$$, then the $$$i$$$-th letter of the string $$$t$$$ is maximal, so we know that the $$$i$$$-th letter affect all $$$b_j \ne 0$$$. While the string $$$t$$$ is not completely constructed, we will do the following:
• Find all $$$i$$$ such that $$$b_i = 0$$$ and the $$$i$$$-th character of string $$$t$$$ is not placed;
• Put on all these positions $$$i$$$ in the string $$$t$$$ the maximum letter not used in the string $$$t$$$ (there should be a sufficient number of letters in the string $$$s$$$);
• Subtract $$$|i - j|$$$ from all $$$b_j \ne 0$$$.