Little Cyan Fish mag die Stringtheorie sehr. Heute lädt dich Little Cyan Fish ein, gemeinsam mit ihm menschliche Spitznamen zu untersuchen.

Im Universum von Little Cyan Fish können menschliche Spitznamen alle als eine Zeichenkette dargestellt werden, die nur lateinische Kleinbuchstaben (a bis z) enthält. Zum Beispiel sind qingyu und xiuga menschliche Spitznamen, aber Abacde ist kein menschlicher Spitzname.

Als Mensch ist dein aktueller Spitzname die Zeichenkette $s_0$. Little Cyan Fish bietet den Menschen $n$ Arten von Umbenennungsmöglichkeiten an, wobei die $i$-te Umbenennungsmöglichkeit durch eine positive ganze Zahl $\ell_i$ dargestellt werden kann. Du kannst diese Umbenennungsoperationen in beliebiger Reihenfolge ausführen, aber jede Umbenennungsoperation muss genau einmal ausgeführt werden.

Wenn du dich entscheidest, die $i$-te Art der Umbenennungsoperation zu verwenden, wird dein Name $s$ zu den ersten $\ell_i$ Zeichen von $s^\omega$, wobei $s^\omega$ die Zeichenkette bezeichnet, die durch unendlich häufiges Aneinanderhängen der Zeichenkette $s$ entsteht. Wenn dein aktueller Name beispielsweise $s = \text{ad}$ lautet, wird dein Name nach dem Ausführen der Umbenennungsoperation mit $\ell = 5$ zu $s' = \text{adada}$.

Little Cyan Fish möchte, dass menschliche Spitznamen lexikografisch so groß wie möglich werden. Nun gibt dir Little Cyan Fish $s_0$ sowie $\ell_1, \ell_2, \dots, \ell_n$. Du musst eine Umbenennungsreihenfolge $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, $p_i$ ist eine Permutation der Länge $n$) finden, sodass nach dem Umbenennen in der Reihenfolge $\ell_{p_1}, \ell_{p_2}, \dots, \ell_{p_n}$ die am Ende erhaltene Zeichenkette die größtmögliche lexikografische Ordnung hat.

Eingabe

Es gibt mehrere Testfälle. Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl $T$ ($1 \le T$), die die Anzahl der Testfälle angibt.

Für jeden Testfall enthält die erste Zeile der Eingabe eine Zeichenkette $s_0$ ($1 \le |s_0| \le 10^5$, $s_0$ enthält nur lateinische Kleinbuchstaben), die deinen anfänglichen Spitznamen angibt.

Die nächste Zeile enthält eine ganze Zahl $n$ ($1 \le n \le 10^5$), die die Anzahl der Umbenennungsmöglichkeiten angibt.

Die nächste Zeile enthält $n$ ganze Zahlen $\ell_1, \ell_2, \dots, \ell_n$ ($1 \le \ell_i \le 10^9$), die die Parameter jeder Umbenennungsmöglichkeit angeben.

Es wird garantiert, dass die Summe von $|s_0|$ über alle Testfälle $10^5$ nicht überschreitet, und dass die Summe von $n$ über alle Testfälle $10^5$ nicht überschreitet.

Ausgabe

Gib für jeden Testfall eine einzelne Zeile mit $n$ ganzen Zahlen $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, $p_i$ ist eine Permutation der Länge $n$) aus, die deine Umbenennungsreihenfolge angibt.

Beispiel

Eingabe 1

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

Ausgabe 1

2 1
1 2
3 6 2 1 4 5