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.


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

Difficulty: introductory

Starter code:

Solutions:
import sys
input = sys.stdin.readline

t=int(input())
for tests in range(t):
    S=input().strip()
    m=int(input())
    B=list(map(int,input().split()))

    LIST=[0]*26

    for s in S:
        LIST[ord(s)-97]+=1

    ANS=[0]*m
    ind=25

    while max(B)>=0:
        L=[]
        for i in range(m):
            if B[i]==0:
                L.append(i)
                B[i]=-1

        LEN=len(L)

        while LIST[ind]<LEN:
            ind-=1

        for l in L:
            ANS[l]=ind

        ind-=1

        for l in L:
            for i in range(m):
                B[i]-=abs(i-l)

    #print(ANS)
    print("".join([chr(a+97) for a in ANS]))
                
        

    

    
    


from math import *

def r1(t):
    return t(input())

def r2(t):
    return [t(i) for i in input().split()]

def r3(t):
    return [t(i) for i in input()]

for _ in range(r1(int)):
    s = r3(str)
    m = r1(int)
    b = r2(int)

    s.sort()
    mp = {}
    for i in s:
        mp[i] = 0
    for i in s:
        mp[i] += 1
    
    t = ['' for i in range(m)]
    for i in range(m):
        ind = []
        cnt = 0
        for j in range(m):
            if b[j] == 0:
                ind.append(j)
                cnt += 1
        if (cnt == 0):
            break
        for x in ind:
            for j in range(m):
                b[j] -= max(abs(x - j), 1)

        tk = ''
        tkeys = list(sorted(list(mp.keys()), reverse=True))
        for k in tkeys:
            if mp[k] >= len(ind):
                tk = k
            del mp[k]
            if len(tk) > 0:
                break
            
        for x in ind:
            t[x] = tk
        #print(mp, b, t)

    print(''.join(t))


for _ in range(int(input())):
    s = input()
    m = int(input())
    b = list(map(int,input().split()))
    values = {}
    for num in b:
        if num not in values:
            values[num] = 0
        values[num] += 1
    letters = {}
    for c in s:
        if c not in letters:
            letters[c] = 0
        letters[c] += 1
    sortedLetters = []
    sortedValues = []
    for elem in letters:
        sortedLetters.append((elem, letters[elem]))
    sortedLetters.sort()
    ans = ["" for _ in range(m)]
    while True:
        done = True
        toChange = []
        for i in range(m):
            dist = 0
            if ans[i] != "":
                continue
            for j in range(m):
                if ans[j] != "":
                    dist += abs(i-j)
            if dist == b[i]:
                toChange.append(i)
        if len(toChange) == 0:
            break
        cnt = len(toChange)
        while sortedLetters[-1][1] < cnt:
            sortedLetters.pop(-1)
        for i in toChange:
            ans[i] = sortedLetters[-1][0]
        sortedLetters.pop(-1)
    print("".join(ans))


t=int(input())
for _ in range(t):
    s=input()
    m=int(input())
    b=list(map(int,input().split()))
    slist=[]
    for i in range(len(s)):
        slist.append(s[i])
    slist.sort()
    slist.reverse()
    slist2=[]
    slist2.append([slist[0],1])
    for i in range(1,len(s)):
        if slist2[-1][0]==slist[i]:
            slist2[-1][1]+=1
        else:
            slist2.append([slist[i],1])
    pointer=0
    done=[0]*m
    ans=[0]*m
    while sum(done)<m:
        zeros=[]
        for i in range(m):
            if b[i]==0 and done[i]==0:
                zeros.append(i)
        num=len(zeros)
        while slist2[pointer][1]<num:
            pointer+=1
        for i in zeros:
            done[i]=1
            ans[i]=slist2[pointer][0]
            for j in range(m):
                b[j]-=abs(i-j)
        pointer+=1
    print(''.join(ans))

T = int(input())
for _ in range(T):
    s = input()
    m = int(input())
    b = [int(s) for s in input().split()]
    count = [0] * 26
    for c in s:
        count[ord(c) - 97] += 1
    res = [''] * m
    p = 0
    while p < m:
        zeros = []
        for i in range(m):
            if b[i] == 0:
                zeros.append(i)
        for i in range(25,-1,-1):
            if count[i] >= len(zeros):
                c = chr(i + 97)
                count[i] = 0
                break
            else:
                count[i] = 0
        for zero in zeros:
            res[zero] = c
            b[zero] = -1
            for i in range(m):
                b[i] -= abs(i - zero)
        p += len(zeros)
    print(''.join(res))

from collections import Counter

T = int(input())

for t in range(T):
    S = input()
    M = int(input())
    B = [int(_) for _ in input().split()]

    Y = ['' for _ in range(M)]
    expected_scores = [0] * M
    cc = Counter(S)
    for _c in range(ord('z'), ord('a')-1, -1):
        c = chr(_c)
        if not cc[c]:
            continue
        # print('before', c, Y, expected_scores)
        poss = []
        next_expected_scores = list(expected_scores)
        for pos in range(M):
            if Y[pos] != '':
                continue
            if B[pos] == expected_scores[pos]:
                poss.append(pos)
                for p in range(M):
                    next_expected_scores[p] += abs(p-pos)

        if len(poss) <= cc[c]:
            expected_scores = next_expected_scores
            for p in poss:
                Y[p] = c
        # print('after', c, Y, expected_scores)

    print(''.join(Y))


tests = int(input())
for _ in range(tests):
    s = input()
    n = int(input())
    b = list(map(int, input().split()))
    g = sorted(b)
    ans = ['a'] * n
    d = dict()
    for i in set(s):
        d[i] = 0
    for i in s:
        d[i] += 1
    tec = 122
    r = b.count(0)
    while r != 0:
        flag = True
        while flag:
            if chr(tec) in d:
                if d[chr(tec)] >= r:
                    flag = False
                    break
            tec -= 1
        sp = []
        for i in range(n):
            if b[i] == 0:
                sp.append(i)
                b[i] = -1
        for i in range(n):
            summ = 0
            if b[i] < 0:
                continue
            for j in sp:
                summ += abs(i - j)
            b[i] -= summ
        for i in sp:
            ans[i] = chr(tec)
        tec -= 1
        r = b.count(0)
    for i in ans:
        print(i, end ='')
    print()


m=10**9+7
t = int(input())
while(t):
    t-=1
    s=input()
    m = int(input())
    b = list(map(int,input().split()))
    fin = sorted(s)
    ans=[""]*m
    while "" in ans:
        new=[index for index, value in enumerate(b) if value == 0]
        while fin.count(fin[-1])<len(new):
            fin = list(filter(lambda x: x != fin[-1], fin))
        for i in new:
            b[i]=-1
            ans[i]=fin[-1]
        fin = list(filter(lambda x: x != fin[-1], fin))
        for i in range(len(b)):
            if b[i]!=-1:
                for j in new:
                    b[i] -= abs(i-j)
    print("".join(ans))

from collections import Counter
q = int(input())
for _ in range(q):
    s = input()
    m = int(input())
    b = list(map(int, input().split()))
    c = Counter(s)
    c = list(c.items())
    c.sort(key=lambda x: x[0])

    ans = [None for _ in range(m)]
    while not all(ans):
        indices = []
        for i in range(m):
            if b[i] == 0:
                indices.append(i)
                b[i] = -1
        while True:
            if c[-1][1] >= len(indices):
                for idx in indices:
                    ans[idx] = c[-1][0]
                c.pop()
                break
            else:
                c.pop()
            
        for j in range(m):
            for idx in indices:
                b[j] -= abs(idx-j)
    print(''.join(map(str, ans)))
        


import sys

inp = [x for x in sys.stdin.read().split()]; ii = 0

ttt = int(inp[ii]); ii += 1
for _ in range(ttt):
	s, m = inp[ii], int(inp[ii + 1]); ii += 2
	b = [int(x) for x in inp[ii: ii + m]]; ii += m
	cnt = [0] * 26
	for c in s:
		cnt[ord(c) - ord('a')] += 1
	res = [-1] * m
	for c in range(25, -1, -1):
		cur_ind = []
		for i in range(m):
			if res[i] == -1:
				cur_sum = 0
				for j in range(m):
					if res[j] != -1:
						cur_sum += abs(i - j)
				if cur_sum == b[i]:
					cur_ind.append(i)
		if len(cur_ind) <= cnt[c]:
			for i in cur_ind:
				res[i] = c
	print("".join(chr(c + ord('a')) for c in res))

from sys import stdin, stdout, setrecursionlimit
for _ in range(int(input())):
    s = input()
    n = int(input())
    a = [int(i) for i in input().split()]
    l = {}
    for x in s:
        if x not in l:
            l[x] = 1
        else:
            l[x] += 1
    s = set(s)
    t = ""
    for x in s:
        t += x
    t = sorted(t, reverse=True)
    ans = [0] * n
    j = 1
    h = {}
    while 0 in ans:
        cur = []
        for i in range(n):
            if a[i] == 0 and ans[i] == 0:
                ans[i] = j
                cur.append(i)
        for i in range(n):
            if ans[i] > 0:
                continue
            for x in cur:
                a[i] -= abs(i - x)
        h[j] = len(cur)
        j += 1

    itog = [0] * n
    curi = 0
    for key in h:
        while l[t[curi]] < h[key]:
            curi += 1
        for i in range(n):
            if ans[i] == key:
                itog[i] = t[curi]
        curi += 1
    for x in itog:
        print(x, end ="")
    print()

def alldone(l):
    for i in l:
        if(i==0):
            return 0
    return 1
t=int(input())
for you in range(t):
    s=input()
    freq=[0 for i in range(26)]
    done=[0 for i in range(26)]
    for i in s:
        freq[ord(i)-97]+=1
    n=int(input())
    l=input().split()
    li=[int(i) for i in l]
    fist=[0 for i in range(n)]
    lfi=[]
    l=[]

    donefors=[0 for i in range(n)]
    for i in range(n):
        if(li[i]==0):
            l.append(i)
            donefors[i]=1
            lfi.append(i)
    for i in range(25,-1,-1):
        if(freq[i]>=len(l) and done[i]==0):
            done[i]=1
            for j in l:
                fist[j]=chr(97+i)
            l=[]
            break
        else:
            done[i]=1
    while(alldone(donefors)==0):
        for i in range(n):
            if(donefors[i]==1):
                continue
            else:
                z=li[i]
                for j in lfi:
                    li[i]=li[i]-abs(i-j)
                if(li[i]==0):
                    continue
                li[i]=z
        for i in range(n):
            if(li[i]==0 and donefors[i]==0):
                l.append(i)
                donefors[i]=1
        for i in l:
            lfi.append(i)


        for i in range(25,-1,-1):
            if(freq[i]>=len(l) and done[i]==0):
                done[i]=1
                for j in l:
                    fist[j]=chr(97+i)
                l=[]
                break
            else:
                done[i]=1
    for i in fist:
        print(i,end="")
    print()

import sys
import collections

input = sys.stdin.readline


def main():
    t = int(input())
    for _ in range(t):
        S = input().strip()
        M = int(input())
        B = [int(x) for x in input().split()]

        c = collections.Counter(S)
        ans = [""] * M
        ans_rank = [-1] * M
        current = 0

        while sum(B) != -M:
            zero = []
            for i in range(M):
                if B[i] == 0:
                    zero.append(i + 1)
                    B[i] = -1
                    ans_rank[i] = current

            current += 1
            for i in range(M):
                if B[i] == -1:
                    continue
                for z in zero:
                    B[i] -= abs(i + 1 - z)


        for i in range(M):
            if ans_rank[i] == -1:
                ans_rank[i] = current

        c_rank = collections.Counter(ans_rank)

        ma = max(ans_rank)
        c_s = 26
        for i in range(ma + 1):
            ccr = c_rank[i]
            while c[chr(ord('a') + c_s)] < ccr:
                c_s -= 1

            for j in range(M):
                if ans_rank[j] == i:
                    ans[j] = chr(ord('a') + c_s)
            c_s -= 1

        print("".join(ans))


def __starting_point():
    main()

__starting_point()

def main():
    q = int(input())
    for _ in range(q):
        s = input()
        m = int(input())
        t = ["0" for __ in range(m)]
        b = list(map(int, input().split()))
        l = sorted(s)
        d = {}
        for x in s:
            if x in d:
                d[x] += 1
            else:
                d[x] = 1
        while True:
            idxs = []; num0s = 0
            for c, el in enumerate(b):
                if el == 0:
                    num0s += 1
                    #t[c] = l.pop()
                    idxs.append(c)
                    b[c] = -1
            if not num0s:
                break
            while True:
                chosen = l[-1]
                freq = d[chosen]
                if freq < num0s:
                    l = l[:-freq]
                else:
                    for ix in idxs:
                        t[ix] = chosen
                    l = l[:-freq]
                    break
            for i in range(len(b)):
                for idx in idxs:
                    b[i] -= abs(i - idx)
            #print(b)
        print("".join(t))
main()

import sys
from collections import Counter as CO
from collections import defaultdict as dd
input=sys.stdin.readline
t=int(input())
for _ in range(t):
    word=list(map(str,input().strip()))
    df=dd(int)
    for k in word:
        df[k]+=1
        
    n=int(input())
    arr=list(map(int,input().split()))
    d=dict()
    l=[]
    maxi=[]
    while(sum(arr)!=0):
        for i in range(len(arr)):
            if(arr[i]==0 and i not in d):
                maxi+=[i]
                d[i]=1
        l+=[maxi]
        for i in maxi:
            for j in range(len(arr)):
                if(arr[j]!=0):
                    arr[j]-=abs(i-j)
        maxi=[]
    for i in  range(len(arr)):
        if(arr[i]==0 and i not in d):
            maxi+=[i]
    
    l+=[maxi]
    ind=0
    final=[0]*n
    for k in sorted(df,reverse=True):
        
        if(ind==len(l)):
            break
        if(len(l[ind])>df[k]):
            continue
        for i in range(len(l[ind])):
            final[l[ind][i]]=k
        ind+=1
    #print(final)       
    print(''.join(final))