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