Little Cyan Fish pitää säieteoriasta (ja merkkijonoteoriasta) erittäin paljon. Tänään Little Cyan Fish kutsuu sinut tutkimaan ihmisten lempinimiä kanssaan.

Little Cyan Fishin maailmankaikkeudessa kaikki ihmisten lempinimet voidaan esittää merkkijonona, joka sisältää vain pieniä latinalaisia kirjaimia (a – z). Esimerkiksi qingyu ja xiuga ovat ihmisten lempinimiä, mutta Abacde ei ole ihmisen lempinimi.

Ihmisenä nykyinen lempinimesi on merkkijono $s_0$. Little Cyan Fish tarjoaa ihmisille $n$ erilaista nimenmuutosmahdollisuutta, joista $i$:ttä nimenmuutosmahdollisuutta kuvaa positiivinen kokonaisluku $\ell_i$. Voit suorittaa nämä nimenmuutosoperaatiot missä tahansa järjestyksessä, mutta jokainen nimenmuutosoperaatio on suoritettava täsmälleen kerran.

Jos päätät käyttää $i$:nnen tyyppistä nimenmuutosoperaatiota, nimestäsi $s$ tulee merkkijonon $s^\omega$ ensimmäiset $\ell_i$ merkkiä, missä $s^\omega$ tarkoittaa merkkijonoa, joka saadaan toistamalla merkkijonoa $s$ äärettömän monta kertaa. Jos esimerkiksi nykyinen nimesi on $s = \text{ad}$, niin suoritettuasi nimenmuutosoperaation arvolla $\ell = 5$ nimeksesi tulee $s' = \text{adada}$.

Little Cyan Fish haluaa ihmisten lempinimistä aakkosjärjestyksessä (leksikografisesti) mahdollisimman suuria. Nyt Little Cyan Fish antaa merkkijonon $s_0$ sekä luvut $\ell_1, \ell_2, \dots, \ell_n$. Sinun tulee etsiä jokin nimenmuutosjärjestys $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, $p_i$ on pituuden $n$ permutaatio), jolla järjestyksessä $\ell_{p_1}, \ell_{p_2}, \dots, \ell_{p_n}$ tehtyjen nimenmuutosten jälkeen lopullinen saatu merkkijono on aakkosjärjestyksessä mahdollisimman suuri.

Syöte

Syötteessä on useita testitapauksia. Syötteen ensimmäinen rivi sisältää yhden kokonaisluvun $T$ ($1 \le T$), joka ilmaisee testitapausten lukumäärän.

Jokaisessa testitapauksessa syötteen ensimmäinen rivi sisältää merkkijonon $s_0$ ($1 \le |s_0| \le 10^5$, $s_0$ sisältää vain pieniä latinalaisia kirjaimia), joka ilmaisee alkuperäisen lempinimesi.

Seuraava rivi sisältää kokonaisluvun $n$ ($1 \le n \le 10^5$), joka ilmaisee nimenmuutosmahdollisuuksien lukumäärän.

Seuraava rivi sisältää $n$ kokonaislukua $\ell_1, \ell_2, \dots, \ell_n$ ($1 \le \ell_i \le 10^9$), jotka ilmaisevat kunkin nimenmuutosmahdollisuuden parametrit.

On taattu, että arvojen $|s_0|$ summa yli kaikkien testitapausten ei ylitä arvoa $10^5$, ja lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $10^5$.

Tuloste

Tulosta jokaista testitapausta kohden yksi rivi, joka sisältää $n$ kokonaislukua $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, $p_i$ on pituuden $n$ permutaatio), jotka ilmaisevat nimenmuutosjärjestyksesi.

Esimerkki

Syöte 1

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

Tuloste 1

2 1
1 2
3 6 2 1 4 5