← 返回题目列表

Codeforces · 1927/B

B. 跟随字符串

中文机器翻译题面 查看原题

Polycarp丢失了由小写拉丁字母组成的长度为$$$n$$$的字符串$$$s$$$,但他仍然有它的踪迹。

字符串 $$$s$$$ 的踪迹是一个由 $$$n$$$ 整数组成的数组 $$$a$$$,其中 $$$a_i$$$ 是 $$$j$$$ ($$$j < i$$$) 这样的索引 $$$s_i=s_j$$$ 的数量。例如,字符串 abracadabra 的踪迹是数组 [$$$0, 0, 0, 1, 0, 2, 0, 3, 1, 1, 4$$$]。

给定一个字符串的踪迹,找到可以从中获取该字符串的任何字符串 $$$s$$$。字符串 $$$s$$$ 应仅包含小写拉丁字母 a-z。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。然后是测试用例的描述。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 丢失字符串的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i < n$$$) - 字符串的踪迹。保证对于给定的跟踪,存在合适的字符串$$$s$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出与给定跟踪相对应的字符串 $$$s$$$。如果有多个这样的字符串$$$s$$$,则输出其中任何一个。

字符串 $$$s$$$ 应由小写拉丁字母 a-z 组成。

保证对于每个测试用例,都存在有效的答案。

示例

输入 #1

5
11
0 0 0 1 0 2 0 3 1 1 4
10
0 0 0 0 0 1 0 1 1 0
1
0
8
0 1 2 3 4 5 6 7
8
0 0 0 0 0 0 0 0

输出 #1

abracadabra
codeforces
a
aaaaaaaa
dijkstra