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