A Little Cyan Fish piace molto la teoria delle stringhe. Oggi, Little Cyan Fish ti invita a studiare insieme a lui i soprannomi umani.

Nell'universo di Little Cyan Fish, tutti i soprannomi umani possono essere rappresentati come una stringa contenente solo lettere latine minuscole (da a a z). Ad esempio, qingyu e xiuga sono soprannomi umani, ma Abacde non è un soprannome umano.

Come essere umano, il tuo soprannome attuale è la stringa $s_0$. Little Cyan Fish offre agli umani $n$ tipi di opportunità di cambio nome; la $i$-esima opportunità di cambio nome può essere rappresentata da un intero positivo $\ell_i$. Puoi eseguire queste operazioni di cambio nome in qualsiasi ordine, ma ciascuna operazione di cambio nome deve essere eseguita esattamente una volta.

Se scegli di utilizzare il $i$-esimo tipo di operazione di cambio nome, allora il tuo nome $s$ diventerà i primi $\ell_i$ caratteri di $s^\omega$, dove $s^\omega$ indica la stringa ottenuta copiando la stringa $s$ infinite volte. Ad esempio, se il tuo nome attuale è $s = \text{ad}$, dopo aver eseguito l'operazione di cambio nome con $\ell = 5$, il tuo nome diventerà $s' = \text{adada}$.

Little Cyan Fish vuole che i soprannomi umani diventino lessicograficamente più grandi possibile. Ora, Little Cyan Fish ti dà $s_0$ e $\ell_1, \ell_2, \dots, \ell_n$. Devi trovare un ordine di cambio nome $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, $p_i$ è una permutazione di lunghezza $n$), tale che dopo aver cambiato nome nell'ordine $\ell_{p_1}, \ell_{p_2}, \dots, \ell_{p_n}$, la stringa finale ottenuta abbia il più grande ordine lessicografico possibile.

Input

Ci sono più casi di test. La prima riga dell'input contiene un singolo intero $T$ ($1 \le T$), che indica il numero di casi di test.

Per ogni caso di test, la prima riga dell'input contiene una stringa $s_0$ ($1 \le |s_0| \le 10^5$, $s_0$ contiene solo lettere latine minuscole), che indica il tuo soprannome iniziale.

La riga successiva contiene un intero $n$ ($1 \le n \le 10^5$), che indica il numero di opportunità di cambio nome.

La riga successiva contiene $n$ interi $\ell_1, \ell_2, \dots, \ell_n$ ($1 \le \ell_i \le 10^9$), che indicano i parametri di ciascuna opportunità di cambio nome.

È garantito che la somma di $|s_0|$ su tutti i casi di test non supera $10^5$, e che la somma di $n$ su tutti i casi di test non supera $10^5$.

Output

Per ogni caso di test, stampa una singola riga contenente $n$ interi $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, $p_i$ è una permutazione di lunghezza $n$), che indicano il tuo ordine di cambio nome.

Esempio

Input 1

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

Output 1

2 1
1 2
3 6 2 1 4 5