Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Task On The Board

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputPolycarp 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.

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

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.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/16/2021 06:26:16 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|