Little Cyan Fish дуже любить теорію струн (і рядків). Сьогодні Little Cyan Fish запрошує вас разом із ним дослідити людські прізвиська.

У всесвіті Little Cyan Fish усі людські прізвиська можна подати у вигляді рядка, що містить лише малі латинські літери (від a до z). Наприклад, qingyu, xiuga — це людські прізвиська, а Abacde не є людським прізвиськом.

Оскільки ви людина, ваше поточне прізвисько — це рядок $s_0$. Little Cyan Fish пропонує людям $n$ видів можливостей перейменування, причому $i$-ту можливість перейменування можна подати додатним цілим числом $\ell_i$. Ви можете виконувати ці операції перейменування в будь-якому порядку, але кожна операція перейменування має бути виконана рівно один раз.

Якщо ви вирішите використати операцію перейменування $i$-го виду, то ваше ім'я $s$ перетвориться на перші $\ell_i$ символів рядка $s^\omega$, де $s^\omega$ позначає рядок, отриманий нескінченним копіюванням рядка $s$. Наприклад, якщо ваше поточне ім'я $s = \text{ad}$, то після виконання операції перейменування з $\ell = 5$ ваше ім'я стане $s' = \text{adada}$.

Little Cyan Fish хоче, щоб людські прізвиська стали лексикографічно якомога більшими. Тепер Little Cyan Fish дає $s_0$ та $\ell_1, \ell_2, \dots, \ell_n$. Вам потрібно знайти деякий порядок перейменування $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, $p_i$ — перестановка довжини $n$), такий що після перейменування в порядку $\ell_{p_1}, \ell_{p_2}, \dots, \ell_{p_n}$ кінцевий отриманий рядок матиме найбільший можливий лексикографічний порядок.

Вхідні дані

Є декілька наборів вхідних даних. Перший рядок вхідних даних містить одне ціле число $T$ ($1 \le T$), що вказує на кількість наборів вхідних даних.

Для кожного набору вхідних даних перший рядок містить рядок $s_0$ ($1 \le |s_0| \le 10^5$, $s_0$ містить лише малі латинські літери), що позначає ваше початкове прізвисько.

Наступний рядок містить ціле число $n$ ($1 \le n \le 10^5$), що вказує на кількість можливостей перейменування.

Наступний рядок містить $n$ цілих чисел $\ell_1, \ell_2, \dots, \ell_n$ ($1 \le \ell_i \le 10^9$), що позначають параметри кожної можливості перейменування.

Гарантується, що сума $|s_0|$ за всіма наборами вхідних даних не перевищує $10^5$, і сума $n$ за всіма наборами вхідних даних не перевищує $10^5$.

Вихідні дані

Для кожного набору вхідних даних виведіть один рядок, що містить $n$ цілих чисел $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, $p_i$ — перестановка довжини $n$), які позначають ваш порядок перейменування.

Приклад

Вхідні дані 1

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

Вихідні дані 1

2 1
1 2
3 6 2 1 4 5