小青魚非常喜歡字串理論。今天，小青魚邀請你和他一起研究人類的綽號。

在小青魚的宇宙裡，人類的綽號都可以表示為僅包含小寫拉丁字母（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