Little Cyan Fish tycker väldigt mycket om strängteori. Idag bjuder Little Cyan Fish in dig att studera mänskliga smeknamn tillsammans med honom.

I Little Cyan Fishs universum kan alla mänskliga smeknamn representeras som en sträng som endast innehåller små latinska bokstäver (a till z). Till exempel är qingyu och xiuga mänskliga smeknamn, men Abacde är inte ett mänskligt smeknamn.

Som människa är ditt nuvarande smeknamn strängen $s_0$. Little Cyan Fish erbjuder människor $n$ typer av namnbytesmöjligheter, där den $i$:te namnbytesmöjligheten kan representeras av ett positivt heltal $\ell_i$. Du kan utföra dessa namnbytesoperationer i valfri ordning, men varje namnbytesoperation måste utföras exakt en gång.

Om du väljer att använda den $i$:te typen av namnbytesoperation kommer ditt namn $s$ att bli de första $\ell_i$ tecknen i $s^\omega$, där $s^\omega$ betecknar strängen som erhålls genom att kopiera strängen $s$ oändligt många gånger. Om ditt nuvarande namn till exempel är $s = \text{ad}$, så kommer ditt namn efter att ha utfört namnbytesoperationen med $\ell = 5$ att bli $s' = \text{adada}$.

Little Cyan Fish vill att mänskliga smeknamn ska bli så lexikografiskt stora som möjligt. Nu ger Little Cyan Fish dig $s_0$ och $\ell_1, \ell_2, \dots, \ell_n$. Du måste hitta en namnbytesordning $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, $p_i$ är en permutation med längden $n$), sådan att efter namnbyte i ordningen $\ell_{p_1}, \ell_{p_2}, \dots, \ell_{p_n}$ har den slutliga erhållna strängen den största möjliga lexikografiska ordningen.

Indata

Det finns flera testfall. Den första raden i indata innehåller ett enda heltal $T$ ($1 \le T$), som anger antalet testfall.

För varje testfall innehåller den första raden i indata en sträng $s_0$ ($1 \le |s_0| \le 10^5$, $s_0$ innehåller endast små latinska bokstäver), som anger ditt ursprungliga smeknamn.

Nästa rad innehåller ett heltal $n$ ($1 \le n \le 10^5$), som anger antalet namnbytesmöjligheter.

Nästa rad innehåller $n$ heltal $\ell_1, \ell_2, \dots, \ell_n$ ($1 \le \ell_i \le 10^9$), som anger parametrarna för varje namnbytesmöjlighet.

Det garanteras att summan av $|s_0|$ över alla testfall inte överstiger $10^5$, och att summan av $n$ över alla testfall inte överstiger $10^5$.

Utdata

För varje testfall, skriv ut en enda rad som innehåller $n$ heltal $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, $p_i$ är en permutation med längden $n$), vilka anger din namnbytesordning.

Exempel

Indata 1

3
qingyu
2
7 3
abacde
2
8 11
abcabadefdghiajkd
6
11 4 5 14 1919 810

Utdata 1

2 1
1 2
3 6 2 1 4 5