Common Prefixes

1000ms

262144K

Description:

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:

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:

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.

Sample Input:

Sample Output:

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

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$$$

Informação

Provedor Codeforces

Código CF1384A