Little Cyan Fish は弦理論（文字列理論）が大好きです。今日、Little Cyan Fish はあなたを誘って一緒に人間のニックネームについて研究することにしました。

Little Cyan Fish の宇宙では、人間のニックネームはすべて英小文字（a から z）のみを含む文字列として表すことができます。例えば、qingyu や xiuga は人間のニックネームですが、Abacde は人間のニックネームではありません。

人間であるあなたの現在のニックネームは文字列 $s_0$ です。Little Cyan Fish は人間に $n$ 種類の改名の機会を提供します。$i$ 番目の改名の機会は正の整数 $\ell_i$ で表されます。これらの改名操作は任意の順序で実行できますが、各改名操作はちょうど 1 回ずつ実行しなければなりません。

$i$ 番目の種類の改名操作を使用することにした場合、あなたの名前 $s$ は $s^\omega$ の先頭 $\ell_i$ 文字になります。ここで、$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$ が与えられます。$\ell_{p_1}, \ell_{p_2}, \dots, \ell_{p_n}$ の順序で改名を行った後に得られる最終的な文字列が辞書順で最大となるような、改名順序 $p_1, p_2, \dots, p_n$（$1 \le p_i \le n$、$p_i$ は長さ $n$ の順列）を求めてください。

入力

複数のテストケースがあります。入力の 1 行目には、テストケースの個数を表す 1 つの整数 $T$（$1 \le T$）が与えられます。

各テストケースについて、入力の 1 行目にはあなたの最初のニックネームを表す文字列 $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 行に出力せよ。

入出力例

入力例 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