#P17965. Call You With Your Name

Call You With Your Name

给定一个仅包含小写英文字母的字符串 s0s_0 和 nn 个正整数 ℓ1,…,ℓn\ell_1,\ldots,\ell_n。

第 ii 个操作将当前字符串 ss 改为 sωs^\omega 的前 ℓi\ell_i 个字符,其中 sωs^\omega 表示将 ss 无限重复得到的字符串。例如,对 ad 执行长度为 55 的操作后得到 adada。

你需要将每个操作恰好执行一次,顺序可以任意安排。输出一个操作编号的排列,使最终字符串的字典序最大。

字典序采用通常定义:在第一个不同字符处比较字符大小;若一个字符串是另一个字符串的真前缀,则较短者较小。

输入格式

第一行是测试用例数 T≥1T\ge1。每组数据包含三行:

  • 第一行字符串 s0s_0;
  • 第二行操作个数 nn;
  • 第三行 nn 个整数 ℓ1,…,ℓn\ell_1,\ldots,\ell_n。

1≤∣s0∣,n≤1051\le|s_0|,n\le10^5,1≤ℓi≤1091\le\ell_i\le10^9。所有测试用例的 ∣s0∣|s_0| 之和、nn 之和分别不超过 10510^5。

输出格式

每组数据输出一行 nn 个整数 p1,…,pnp_1,\ldots,p_n,它们必须是 1,…,n1,\ldots,n 的一个排列。按照此顺序执行操作后,最终字符串须达到最大字典序。如果有多种最优排列,输出任意一种。

样例输入

3
qingyu
2
7 3
abacde
2
8 11
abcabadefdghiajkd
6
11 4 5 14 1919 810

样例输出

2 1
1 2
3 6 2 1 4 5