Little Cyan Fish bardzo lubi teorię strun (i napisów). Dzisiaj Little Cyan Fish zaprasza cię do wspólnego badania ludzkich pseudonimów.

We wszechświecie Little Cyan Fish wszystkie ludzkie pseudonimy można przedstawić jako napis zawierający wyłącznie małe litery alfabetu łacińskiego (od a do z). Na przykład qingyu, xiuga są ludzkimi pseudonimami, ale Abacde nie jest ludzkim pseudonimem.

Jako człowiek masz obecnie pseudonim będący napisem $s_0$. Little Cyan Fish oferuje ludziom $n$ rodzajów możliwości zmiany imienia; $i$-tą możliwość zmiany imienia można przedstawić za pomocą dodatniej liczby całkowitej $\ell_i$. Możesz wykonać te operacje zmiany imienia w dowolnej kolejności, ale każda operacja zmiany imienia musi zostać wykonana dokładnie raz.

Jeśli zdecydujesz się użyć $i$-tego rodzaju operacji zmiany imienia, to twoje imię $s$ stanie się pierwszymi $\ell_i$ znakami napisu $s^\omega$, gdzie $s^\omega$ oznacza napis uzyskany przez skopiowanie napisu $s$ nieskończenie wiele razy. Na przykład, jeśli twoje obecne imię to $s = \text{ad}$, to po wykonaniu operacji zmiany imienia z $\ell = 5$ twoje imię stanie się $s' = \text{adada}$.

Little Cyan Fish chce, aby ludzkie pseudonimy stały się jak największe leksykograficznie. Teraz Little Cyan Fish podaje $s_0$ oraz $\ell_1, \ell_2, \dots, \ell_n$. Musisz znaleźć pewną kolejność zmiany imienia $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, $p_i$ jest permutacją o długości $n$), taką że po zmianie imienia w kolejności $\ell_{p_1}, \ell_{p_2}, \dots, \ell_{p_n}$, ostatecznie otrzymany napis ma największy możliwy porządek leksykograficzny.

Wejście

Istnieje wiele przypadków testowych. Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $T$ ($1 \le T$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego pierwszy wiersz wejścia zawiera napis $s_0$ ($1 \le |s_0| \le 10^5$, $s_0$ zawiera tylko małe litery alfabetu łacińskiego), oznaczający twój początkowy pseudonim.

Następny wiersz zawiera liczbę całkowitą $n$ ($1 \le n \le 10^5$), oznaczającą liczbę możliwości zmiany imienia.

Następny wiersz zawiera $n$ liczb całkowitych $\ell_1, \ell_2, \dots, \ell_n$ ($1 \le \ell_i \le 10^9$), oznaczających parametry każdej możliwości zmiany imienia.

Gwarantuje się, że suma $|s_0|$ po wszystkich przypadkach testowych nie przekracza $10^5$, a suma $n$ po wszystkich przypadkach testowych nie przekracza $10^5$.

Wyjście

Dla każdego przypadku testowego wypisz pojedynczy wiersz zawierający $n$ liczb całkowitych $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, $p_i$ jest permutacją o długości $n$), oznaczających twoją kolejność zmiany imienia.

Przykład

Wejście 1

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

Wyjście 1

2 1
1 2
3 6 2 1 4 5