Little Cyan Fish aime beaucoup la théorie des cordes (et des chaînes de caractères). Aujourd'hui, Little Cyan Fish vous invite à étudier les surnoms humains avec lui.

Dans l'univers de Little Cyan Fish, les surnoms humains peuvent tous être représentés par une chaîne contenant uniquement des lettres latines minuscules (a à z). Par exemple, qingyu et xiuga sont des surnoms humains, mais Abacde n'est pas un surnom humain.

En tant qu'humain, votre surnom actuel est la chaîne $s_0$. Little Cyan Fish offre aux humains $n$ types d'opportunités de changement de nom, la $i$-ème opportunité de changement de nom pouvant être représentée par un entier strictement positif $\ell_i$. Vous pouvez exécuter ces opérations de changement de nom dans n'importe quel ordre, mais chaque opération de changement de nom doit être exécutée exactement une fois.

Si vous choisissez d'utiliser le $i$-ème type d'opération de changement de nom, alors votre nom $s$ deviendra les $\ell_i$ premiers caractères de $s^\omega$, où $s^\omega$ désigne la chaîne obtenue en copiant la chaîne $s$ une infinité de fois. Par exemple, si votre nom actuel est $s = \text{ad}$, alors après avoir exécuté l'opération de changement de nom avec $\ell = 5$, votre nom deviendra $s' = \text{adada}$.

Little Cyan Fish souhaite que les surnoms humains deviennent lexicographiquement aussi grands que possible. Maintenant, Little Cyan Fish donne $s_0$ et $\ell_1, \ell_2, \dots, \ell_n$. Vous devez trouver un ordre de changement de nom $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, $p_i$ est une permutation de longueur $n$), tel qu'après avoir changé de nom dans l'ordre $\ell_{p_1}, \ell_{p_2}, \dots, \ell_{p_n}$, la chaîne finale obtenue ait le plus grand ordre lexicographique possible.

Entrée

Il y a plusieurs cas de test. La première ligne de l'entrée contient un seul entier $T$ ($1 \le T$), indiquant le nombre de cas de test.

Pour chaque cas de test, la première ligne de l'entrée contient une chaîne $s_0$ ($1 \le |s_0| \le 10^5$, $s_0$ ne contient que des lettres latines minuscules), indiquant votre surnom initial.

La ligne suivante contient un entier $n$ ($1 \le n \le 10^5$), indiquant le nombre d'opportunités de changement de nom.

La ligne suivante contient $n$ entiers $\ell_1, \ell_2, \dots, \ell_n$ ($1 \le \ell_i \le 10^9$), indiquant les paramètres de chaque opportunité de changement de nom.

Il est garanti que la somme de $|s_0|$ sur l'ensemble des cas de test ne dépasse pas $10^5$, et que la somme de $n$ sur l'ensemble des cas de test ne dépasse pas $10^5$.

Sortie

Pour chaque cas de test, affichez une seule ligne contenant $n$ entiers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, $p_i$ est une permutation de longueur $n$), indiquant votre ordre de changement de nom.

Exemple

Entrée 1

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

Sortie 1

2 1
1 2
3 6 2 1 4 5