Little Cyan Fish жолдар теориясын өте жақсы көреді. Бүгін Little Cyan Fish сізді өзімен бірге адамдардың лақап аттарын зерттеуге шақырады.

Little Cyan Fish әлемінде адамдардың барлық лақап аттарын тек кіші латын әріптерінен (a-дан z-ке дейін) тұратын жол ретінде көрсетуге болады. Мысалы, qingyu, xiuga — адамдардың лақап аттары, ал Abacde адамның лақап аты емес.

Адам ретінде сіздің қазіргі лақап атыңыз — $s_0$ жолы. Little Cyan Fish адамдарға ат өзгертудің $n$ түрлі мүмкіндігін ұсынады, $i$-ші ат өзгерту мүмкіндігін оң бүтін $\ell_i$ санымен көрсетуге болады. Сіз бұл ат өзгерту операцияларын кез келген ретпен орындай аласыз, бірақ әрбір ат өзгерту операциясы дәл бір рет орындалуы керек.

Егер сіз ат өзгерту операциясының $i$-ші түрін пайдалануды таңдасаңыз, онда сіздің $s$ атыңыз $s^\omega$ жолының алғашқы $\ell_i$ таңбасына айналады, мұндағы $s^\omega$ — $s$ жолын шексіз көп рет көшіру арқылы алынған жол. Мысалы, егер сіздің қазіргі атыңыз $s = \text{ad}$ болса, онда $\ell = 5$ болатын ат өзгерту операциясын орындағаннан кейін сіздің атыңыз $s' = \text{adada}$ болады.

Little Cyan Fish адамдардың лақап аттары лексикографиялық тұрғыдан мүмкіндігінше үлкен болғанын қалайды. Енді Little Cyan Fish $s_0$ жолын және $\ell_1, \ell_2, \dots, \ell_n$ сандарын береді. Сізге $\ell_{p_1}, \ell_{p_2}, \dots, \ell_{p_n}$ ретімен ат өзгерткеннен кейін алынған соңғы жолдың лексикографиялық реті мүмкіндігінше ең үлкен болатындай $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, $p_i$ — ұзындығы $n$ болатын орын алмастыру) ат өзгерту ретін табу керек.

Кіріс деректер

Бірнеше тест жағдайлары бар. Кіріс деректердің бірінші қатарында тест жағдайларының санын білдіретін бір бүтін сан $T$ ($1 \le T$) берілген.

Әрбір тест жағдайы үшін кірістің бірінші қатарында сіздің бастапқы лақап атыңызды білдіретін $s_0$ ($1 \le |s_0| \le 10^5$, $s_0$ тек кіші латын әріптерінен тұрады) жолы берілген.

Келесі қатарда ат өзгерту мүмкіндіктерінің санын білдіретін бүтін сан $n$ ($1 \le n \le 10^5$) берілген.

Келесі қатарда әрбір ат өзгерту мүмкіндігінің параметрлерін білдіретін $n$ бүтін сан $\ell_1, \ell_2, \dots, \ell_n$ ($1 \le \ell_i \le 10^9$) берілген.

Барлық тест жағдайлары бойынша $|s_0|$ қосындысы $10^5$-нен аспайтынына және барлық тест жағдайлары бойынша $n$ қосындысы $10^5$-нен аспайтынына кепілдік беріледі.

Шығыс деректер

Әрбір тест жағдайы үшін сіздің ат өзгерту ретіңізді білдіретін $n$ бүтін саннан $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, $p_i$ — ұзындығы $n$ болатын орын алмастыру) тұратын бір қатар шығарыңыз.

Мысал

Кіріс деректер 1

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

Шығыс деректер 1

2 1
1 2
3 6 2 1 4 5