Little Cyan Fish liker strengteori veldig godt. I dag inviterer Little Cyan Fish deg til å studere menneskelige kallenavn sammen med ham.

I Little Cyan Fish sitt univers kan alle menneskelige kallenavn representeres som en streng som kun inneholder små latinske bokstaver (a til z). For eksempel er qingyu og xiuga menneskelige kallenavn, men Abacde er ikke et menneskelig kallenavn.

Som menneske er ditt nåværende kallenavn strengen $s_0$. Little Cyan Fish tilbyr mennesker $n$ typer muligheter for navneendring, der den $i$-te muligheten for navneendring kan representeres av et positivt heltall $\ell_i$. Du kan utføre disse navneendringsoperasjonene i hvilken som helst rekkefølge, men hver navneendringsoperasjon må utføres nøyaktig én gang.

Hvis du velger å bruke den $i$-te typen navneendringsoperasjon, vil navnet ditt $s$ bli de første $\ell_i$ tegnene i $s^\omega$, der $s^\omega$ betegner strengen som oppnås ved å kopiere strengen $s$ uendelig mange ganger. For eksempel, hvis ditt nåværende navn er $s = \text{ad}$, vil navnet ditt etter å ha utført navneendringsoperasjonen med $\ell = 5$ bli $s' = \text{adada}$.

Little Cyan Fish ønsker at menneskelige kallenavn skal bli så leksikografisk store som mulig. Nå gir Little Cyan Fish deg $s_0$ og $\ell_1, \ell_2, \dots, \ell_n$. Du må finne en navneendringsrekkefølge $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, $p_i$ er en permutasjon med lengde $n$), slik at etter navneendring i rekkefølgen $\ell_{p_1}, \ell_{p_2}, \dots, \ell_{p_n}$, har den endelige strengen som oppnås størst mulig leksikografisk orden.

Inndata

Det er flere testtilfeller. Den første linjen av inndataene inneholder et enkelt heltall $T$ ($1 \le T$), som angir antallet testtilfeller.

For hvert testtilfelle inneholder den første linjen av inndataene en streng $s_0$ ($1 \le |s_0| \le 10^5$, $s_0$ inneholder kun små latinske bokstaver), som angir ditt opprinnelige kallenavn.

Den neste linjen inneholder et heltall $n$ ($1 \le n \le 10^5$), som angir antallet muligheter for navneendring.

Den neste linjen inneholder $n$ heltall $\ell_1, \ell_2, \dots, \ell_n$ ($1 \le \ell_i \le 10^9$), som angir parametrene for hver navneendringsmulighet.

Det er garantert at summen av $|s_0|$ over alle testtilfeller ikke overstiger $10^5$, og at summen av $n$ over alle testtilfeller ikke overstiger $10^5$.

Utdata

For hvert testtilfelle, skriv ut én enkelt linje som inneholder $n$ heltall $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, $p_i$ er en permutasjon med lengde $n$), som angir navneendringsrekkefølgen din.

Eksempel

Inndata 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