311051: CF1927B. Following the String

B. Following the Stringtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Polycarp lost the string $s$ of length $n$ consisting of lowercase Latin letters, but he still has its trace.

The trace of the string $s$ is an array $a$ of $n$ integers, where $a_i$ is the number of such indices $j$ ($j < i$) that $s_i=s_j$. For example, the trace of the string abracadabra is the array [$0, 0, 0, 1, 0, 2, 0, 3, 1, 1, 4$].

Given a trace of a string, find any string $s$ from which it could have been obtained. The string $s$ should consist only of lowercase Latin letters a-z.

Input

The first line of the input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then the descriptions of the test cases follow.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the lost string.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i < n$) — the trace of the string. It is guaranteed that for the given trace, there exists a suitable string $s$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output a string $s$ that corresponds to the given trace. If there are multiple such strings $s$, then output any of them.

The string $s$ should consist of lowercase Latin letters a-z.

It is guaranteed that for each test case, a valid answer exists.

ExampleInput

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

Output

abracadabra
codeforces
a
aaaaaaaa
dijkstra

题目大意：
Polycarp 丢失了一个由小写拉丁字母组成的长度为 n 的字符串 s，但他仍然拥有它的“trace”（痕迹）。

字符串 s 的“trace”是一个包含 n 个整数的数组 a，其中 a_i 是满足 s_i=s_j 的索引 j（j < i）的数量。例如，字符串 "abracadabra" 的“trace”是数组 [0, 0, 0, 1, 0, 2, 0, 3, 1, 1, 4]。

给定一个字符串的“trace”，找到任意一个可能产生这个“trace”的字符串 s。字符串 s 应该只包含小写拉丁字母 a-z。

输入数据格式：
输入的第一行包含一个整数 t（1 ≤ t ≤ 10^4）——测试用例的数量。然后是 t 个测试用例的描述。

每个测试用例的第一行包含一个整数 n（1 ≤ n ≤ 2 × 10^5）——丢失字符串的长度。

每个测试用例的第二行包含 n 个整数 a_1, a_2, ..., a_n（0 ≤ a_i < n）——“trace”数组。保证对于给定的“trace”，存在一个合适的字符串 s。

保证所有测试用例的 n 之和不超过 2 × 10^5。

输出数据格式：
对于每个测试用例，输出一个与给定“trace”对应的字符串 s。如果有多个这样的字符串 s，则输出其中任意一个。

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

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

示例：
输入：
```
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
```题目大意： Polycarp 丢失了一个由小写拉丁字母组成的长度为 n 的字符串 s，但他仍然拥有它的“trace”（痕迹）。 字符串 s 的“trace”是一个包含 n 个整数的数组 a，其中 a_i 是满足 s_i=s_j 的索引 j（j < i）的数量。例如，字符串 "abracadabra" 的“trace”是数组 [0, 0, 0, 1, 0, 2, 0, 3, 1, 1, 4]。 给定一个字符串的“trace”，找到任意一个可能产生这个“trace”的字符串 s。字符串 s 应该只包含小写拉丁字母 a-z。 输入数据格式： 输入的第一行包含一个整数 t（1 ≤ t ≤ 10^4）——测试用例的数量。然后是 t 个测试用例的描述。 每个测试用例的第一行包含一个整数 n（1 ≤ n ≤ 2 × 10^5）——丢失字符串的长度。 每个测试用例的第二行包含 n 个整数 a_1, a_2, ..., a_n（0 ≤ a_i < n）——“trace”数组。保证对于给定的“trace”，存在一个合适的字符串 s。 保证所有测试用例的 n 之和不超过 2 × 10^5。 输出数据格式： 对于每个测试用例，输出一个与给定“trace”对应的字符串 s。如果有多个这样的字符串 s，则输出其中任意一个。 字符串 s 应该由小写拉丁字母 a-z 组成。 保证对于每个测试用例，都存在一个有效答案。 示例： 输入： ``` 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 ```