Little Cyan Fish hefur mjög gaman af strengjafræði. Í dag býður Little Cyan Fish þér að rannsaka gælunöfn manna með sér.

Í alheimi Little Cyan Fish er hægt að tákna öll gælunöfn manna sem streng sem inniheldur eingöngu latneska lágstafi (a til z). Til dæmis eru qingyu og xiuga gælunöfn manna, en Abacde er ekki gælunafn manns.

Sem manneskja er núverandi gælunafn þitt strengurinn $s_0$. Little Cyan Fish býður mönnum upp á $n$ tegundir af tækifærum til nafnabreytinga, þar sem $i$-ta tækifærið má tákna með jákvæðri heiltölu $\ell_i$. Þú getur framkvæmt þessar nafnabreytingaraðgerðir í hvaða röð sem er, en hverja nafnabreytingaraðgerð verður að framkvæma nákvæmlega einu sinni.

Ef þú velur að nota $i$-tu tegund nafnabreytingaraðgerðar, þá verður nafnið þitt $s$ að fyrstu $\ell_i$ stöfunum í $s^\omega$, þar sem $s^\omega$ táknar strenginn sem fæst með því að afrita strenginn $s$ óendanlega oft. Til dæmis, ef núverandi nafn þitt er $s = \text{ad}$, þá verður nafnið þitt $s' = \text{adada}$ eftir að nafnabreytingaraðgerðin með $\ell = 5$ hefur verið framkvæmd.

Little Cyan Fish vill að gælunöfn manna verði eins stór í stafrófsröð (lexicographically) og mögulegt er. Nú gefur Little Cyan Fish upp $s_0$ og $\ell_1, \ell_2, \dots, \ell_n$. Þú þarft að finna einhverja nafnabreytingarröð $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, $p_i$ er umröðun af lengd $n$), þannig að eftir nafnabreytingar í röðinni $\ell_{p_1}, \ell_{p_2}, \dots, \ell_{p_n}$ hafi lokastrengurinn sem fæst stærstu mögulegu stafrófsröð.

Inntak

Það eru mörg prófunartilvik. Fyrsta línan í inntakinu inniheldur eina heiltölu $T$ ($1 \le T$), sem gefur til kynna fjölda prófunartilvika.

Fyrir hvert prófunartilvik inniheldur fyrsta línan í inntakinu streng $s_0$ ($1 \le |s_0| \le 10^5$, $s_0$ inniheldur aðeins latneska lágstafi), sem gefur til kynna upphaflegt gælunafn þitt.

Næsta lína inniheldur heiltölu $n$ ($1 \le n \le 10^5$), sem gefur til kynna fjölda tækifæra til nafnabreytinga.

Næsta lína inniheldur $n$ heiltölur $\ell_1, \ell_2, \dots, \ell_n$ ($1 \le \ell_i \le 10^9$), sem gefa til kynna stika hvers tækifæris til nafnabreytingar.

Það er tryggt að summa $|s_0|$ yfir öll prófunartilvik fari ekki yfir $10^5$, og að summa $n$ yfir öll prófunartilvik fari ekki yfir $10^5$.

Úttak

Fyrir hvert prófunartilvik skaltu prenta eina línu sem inniheldur $n$ heiltölur $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, $p_i$ er umröðun af lengd $n$), sem gefa til kynna nafnabreytingarröðina þína.

Dæmi

Inntak 1

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

Úttak 1

2 1
1 2
3 6 2 1 4 5