Polycarp 在黑板上写下了一个字符串 $$$s$$$,仅包含小写拉丁字母 ('a'-'z')。该字符串是您已知的并在输入中给出。
之后,他从字符串 $$$s$$$ 中删除了一些字母,并以任意顺序重写了剩余的字母。结果,他得到了一些新的字符串$$$t$$$。您必须通过一些附加信息来找到它。
假设字符串 $$$t$$$ 的长度为 $$$m$$$,并且字符从左到右编号为 $$$1$$$ 到 $$$m$$$。给定一个 $$$m$$$ 整数序列:$$$b_1, b_2, \ldots, b_m$$$,其中 $$$b_i$$$ 是从索引 $$$i$$$ 到所有此类索引 $$$j$$$ 的距离 $$$|i-j|$$$ 的总和,且 $$$t_j > t_i$$$ (考虑到'a'<'b'<...<'z')。换句话说,为了计算 $$$b_i$$$,Polycarp 找到所有这样的索引 $$$j$$$,其中索引 $$$j$$$ 包含字母表中晚于 $$$t_i$$$ 的字母,并对所有值 $$$|i-j|$$$ 求和。
例如,如果 $$$t$$$ = "abzb",则:
- 由于$$$t_1$$$='a',所有其他索引都包含字母表中靠后的字母,即:$$$b_1=|1-2|+|1-3|+|1-4|=1+2+3=6$$$;
- 由于$$$t_2$$$='b',只有索引$$$j=3$$$包含该字母,该字母在字母表中靠后,即:$$$b_2=|2-3|=1$$$;
- 由于$$$t_3$$$='z',则不存在索引$$$j$$$使得$$$t_j>t_i$$$,因此$$$b_3=0$$$;
- 由于 $$$t_4$$$='b',只有索引 $$$j=3$$$ 包含该字母,该字母在字母表中靠后,即:$$$b_4=|4-3|=1$$$。
因此,如果 $$$t$$$ = "abzb",则 $$$b=[6,1,0,1]$$$。
给定字符串$$$s$$$和数组$$$b$$$,找到同时满足以下两个要求的任何可能的字符串$$$t$$$:
- $$$t$$$ 是通过删除一些字母(可能为零)然后以任意顺序写入其余字母而从 $$$s$$$ 获得的;
- 根据上述规则从字符串 $$$t$$$ 构造的数组,等于输入数据中指定的数组 $$$b$$$。
输入
第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 100$$$) — 测试中的测试用例数量。然后是 $$$q$$$ 测试用例。
每个测试用例由三行组成:
- 第一行包含字符串$$$s$$$,长度从$$$1$$$到$$$50$$$,由小写英文字母组成;
- 第二行包含正整数 $$$m$$$ ($$$1 \le m \le |s|$$$),其中 $$$|s|$$$ 是字符串 $$$s$$$ 的长度,$$$m$$$ 是数组 $$$b$$$ 的长度;
- 第三行包含整数 $$$b_1, b_2, \dots, b_m$$$ ($$$0 \le b_i \le 1225$$$)。
保证在每个测试用例中都存在答案。
输出
输出 $$$q$$$ 行:其中第 $$$k$$$ 行应包含第 $$$k$$$ 测试用例的答案(字符串 $$$t$$$)。保证每个测试用例都有一个答案。如果有多个答案,则输出任意一个。
示例
输入 #1
4 abac 3 2 1 0 abc 1 0 abba 3 1 0 1 ecoosdcefr 10 38 13 24 14 11 5 3 24 17 0
输出 #1
aac b aba codeforces
注意
在第一个测试用例中,这样的字符串 $$$t$$$ 是合适的:“aac”,“aab”。
在第二个测试用例中,这样的字符串 $$$t$$$ 是合适的:“a”,“b”,“c”。
在第三个测试用例中,只有字符串 $$$t$$$ 等于“aba”是合适的,但字符“b”可以来自第二个或第三个位置。