A Little Cyan Fish le gusta mucho la teoría de cuerdas (y de cadenas). Hoy, Little Cyan Fish te invita a estudiar los apodos humanos con él.

En el universo de Little Cyan Fish, todos los apodos humanos pueden representarse como una cadena que contiene únicamente letras latinas minúsculas (a a z). Por ejemplo, qingyu y xiuga son apodos humanos, pero Abacde no es un apodo humano.

Como humano, tu apodo actual es la cadena $s_0$. Little Cyan Fish ofrece a los humanos $n$ tipos de oportunidades de cambio de nombre; la $i$-ésima oportunidad de cambio de nombre se puede representar mediante un entero positivo $\ell_i$. Puedes ejecutar estas operaciones de cambio de nombre en cualquier orden, pero cada operación de cambio de nombre debe ejecutarse exactamente una vez.

Si eliges usar el $i$-ésimo tipo de operación de cambio de nombre, entonces tu nombre $s$ pasará a ser los primeros $\ell_i$ caracteres de $s^\omega$, donde $s^\omega$ denota la cadena obtenida al copiar la cadena $s$ infinitas veces. Por ejemplo, si tu nombre actual es $s = \text{ad}$, entonces después de ejecutar la operación de cambio de nombre con $\ell = 5$, tu nombre se convertirá en $s' = \text{adada}$.

Little Cyan Fish quiere que los apodos humanos sean lexicográficamente lo más grandes posible. Ahora, Little Cyan Fish te da $s_0$ y $\ell_1, \ell_2, \dots, \ell_n$. Debes encontrar algún orden de cambio de nombre $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, $p_i$ es una permutación de longitud $n$), tal que después de cambiar el nombre en el orden $\ell_{p_1}, \ell_{p_2}, \dots, \ell_{p_n}$, la cadena final obtenida tenga el mayor orden lexicográfico posible.

Entrada

Hay múltiples casos de prueba. La primera línea de la entrada contiene un único entero $T$ ($1 \le T$), que indica el número de casos de prueba.

Para cada caso de prueba, la primera línea de la entrada contiene una cadena $s_0$ ($1 \le |s_0| \le 10^5$, $s_0$ solo contiene letras latinas minúsculas), que indica tu apodo inicial.

La siguiente línea contiene un entero $n$ ($1 \le n \le 10^5$), que indica el número de oportunidades de cambio de nombre.

La siguiente línea contiene $n$ enteros $\ell_1, \ell_2, \dots, \ell_n$ ($1 \le \ell_i \le 10^9$), que indican los parámetros de cada oportunidad de cambio de nombre.

Se garantiza que la suma de $|s_0|$ en todos los casos de prueba no supera $10^5$, y que la suma de $n$ en todos los casos de prueba no supera $10^5$.

Salida

Para cada caso de prueba, imprime una sola línea que contenga $n$ enteros $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, $p_i$ es una permutación de longitud $n$), indicando tu orden de cambio de nombre.

Ejemplo

Entrada 1

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

Salida 1

2 1
1 2
3 6 2 1 4 5