题目描述

Polycarp 丢失了一个长度为 $n$ 的字符串 $s$，该字符串仅由小写拉丁字母组成，但他还保留着该字符串的“迹”。

字符串 $s$ 的“迹”是一个长度为 $n$ 的整数数组 $a$，其中 $a_i$ 表示满足 $s_i = s_j$ 且 $j < i$ 的下标 $j$ 的个数。例如，字符串 abracadabra 的迹为 [ 0, 0, 0, 1, 0, 2, 0, 3, 1, 1, 4 ]。

给定一个字符串的迹，请你构造出任意一个可能的原字符串 $s$。$s$ 仅能包含小写拉丁字母 a-z。

输入格式

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来是 $t$ 个测试用例的描述。

每个测试用例的第一行包含一个整数 $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$ 仅能包含小写拉丁字母 a-z。

保证每个测试用例都存在合法解。

说明/提示

由 ChatGPT 4.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

abracadabra
codeforces
a
aaaaaaaa
dijkstra