小青鱼非常喜欢字符串理论。今天，小青鱼邀请你和他一起研究人类的绰号。

在小青鱼的世界里，人类的绰号都可以表示为仅包含小写拉丁字母（a 到 z）的字符串。例如，“qingyu”、“xiuga”是人类的绰号，但“Abacde”不是。

作为人类，你当前的绰号是字符串 $s_0$。小青鱼为人类提供了 $n$ 种改名机会，第 $i$ 种改名机会可以用一个正整数 $\ell_i$ 表示。你可以按任意顺序执行这些改名操作，但每个改名操作必须恰好执行一次。

如果你选择使用第 $i$ 种改名操作，那么你的名字 $s$ 将变为 $s^\omega$ 的前 $\ell_i$ 个字符，其中 $s^\omega$ 表示将字符串 $s$ 复制无限次得到的字符串。例如，如果你当前的名字是 $s = \text{ad}$，那么在执行 $\ell = 5$ 的改名操作后，你的名字将变为 $s' = \text{adada}$。

小青鱼希望人类的绰号在字典序上尽可能大。现在，小青鱼给出了 $s_0$ 和 $\ell_1, \ell_2, \dots, \ell_n$。你需要找到一个改名顺序 $p_1, p_2, \dots, p_n$（$1 \le p_i \le n$，且 $p_1, p_2, \dots, p_n$ 是一个长度为 $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_1, p_2, \dots, p_n$ 是一个长度为 $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