小青魚非常鍾意字符串理論。今日，小青魚邀請你同佢一齊研究人類嘅花名。

喺小青魚嘅宇宙入面，人類嘅花名都可以表示為只包含小寫拉丁字母（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_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