Common Prefixes
Contest: Codeforces Round 659 (Div. 2)
Difficulty rating: 1200
Tags: constructive algorithms, greedy, strings

The length of the longest common prefix of two strings $$$s = s_1 s_2 \ldots s_n$$$ and $$$t = t_1 t_2 \ldots t_m$$$ is defined as the maximum integer $$$k$$$ ($$$0 \le k \le min(n,m)$$$) such that $$$s_1 s_2 \ldots s_k$$$ equals $$$t_1 t_2 \ldots t_k$$$.

Koa the Koala initially has $$$n+1$$$ strings $$$s_1, s_2, \dots, s_{n+1}$$$.

For each $$$i$$$ ($$$1 \le i \le n$$$) she calculated $$$a_i$$$ — the length of the longest common prefix of $$$s_i$$$ and $$$s_{i+1}$$$.

Several days later Koa found these numbers, but she couldn't remember the strings.

So Koa would like to find some strings $$$s_1, s_2, \dots, s_{n+1}$$$ which would have generated numbers $$$a_1, a_2, \dots, a_n$$$. Can you help her?

If there are many answers print any. We can show that answer always exists for the given constraints.

Input format:
Each test contains multiple test cases. The first line contains $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$) — the number of elements in the list $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 50$$$) — the elements of $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$100$$$.

Output format:
For each test case:

Output $$$n+1$$$ lines. In the $$$i$$$-th line print string $$$s_i$$$ ($$$1 \le |s_i| \le 200$$$), consisting of lowercase Latin letters. Length of the longest common prefix of strings $$$s_i$$$ and $$$s_{i+1}$$$ has to be equal to $$$a_i$$$.

If there are many answers print any. We can show that answer always exists for the given constraints.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the $$$1$$$-st test case one of the possible answers is $$$s = [aeren, ari, arousal, around, ari]$$$.

Lengths of longest common prefixes are:

- Between $$$\color{red}{a}eren$$$ and $$$\color{red}{a}ri$$$ $$$\rightarrow 1$$$
- Between $$$\color{red}{ar}i$$$ and $$$\color{red}{ar}ousal$$$ $$$\rightarrow 2$$$
- Between $$$\color{red}{arou}sal$$$ and $$$\color{red}{arou}nd$$$ $$$\rightarrow 4$$$
- Between $$$\color{red}{ar}ound$$$ and $$$\color{red}{ar}i$$$ $$$\rightarrow 2$$$

Example input:
4
4
1 2 4 2
2
5 3
3
1 3 1
3
0 0 0

Example output:
aeren
ari
arousal
around
ari
monogon
monogamy
monthly
kevinvu
kuroni
kurioni
korone
anton
loves
adhoc
problems

Editorial:
The problem asks to find $$$n+1$$$ strings such that $$$LCP(s_i, s_{i + 1}) = a_i$$$ for all $$$i$$$ ($$$1 \le i \le n$$$). A way to solve this problem is the following:
• Set $$$s_1 =$$$ "aaaa...aaaaaaa" (ie. $$$200$$$ times 'a').
• For $$$i$$$ such that ($$$1 \le i \le n$$$) set $$$s_{i + 1} := s_i$$$ and then flip $$$(a_i + 1)$$$-th character of $$$s_{i + 1}$$$ (ie. if it was 'a' put 'b' otherwise 'a'). So for each $$$i$$$:   $$$s_{i}$$$ and $$$s_{i + 1}$$$ will have exactly $$$a_i$$$ common characters from the prefix.  The $$$(a_i + 1)$$$-th character of $$$s_{i+1}$$$ is different than $$$(a_i + 1)$$$-th character of $$$s_i$$$ (this character always exists since $$$0 \le a_i \le 50$$$ and each string has length exactly $$$200$$$).  Therefore the LCP is $$$a_i$$$ as desired.
• $$$s_{i}$$$ and $$$s_{i + 1}$$$ will have exactly $$$a_i$$$ common characters from the prefix.
• The $$$(a_i + 1)$$$-th character of $$$s_{i+1}$$$ is different than $$$(a_i + 1)$$$-th character of $$$s_i$$$ (this character always exists since $$$0 \le a_i \le 50$$$ and each string has length exactly $$$200$$$).
Time complexity: $$$O(n)$$$ per testcase