String Sequence with Specified Borders

You are given a sequence of n positive integers \(a_1,a_2,\dots,a_n\). Your task is to construct a sequence of n+1 non‐empty strings \(S_1,S_2,\dots,S_{n+1}\) (each consisting only of lowercase letters) such that for every \(1\le i\le n\) the following holds:

[ \operatorname{border}(S_iS_{i+1}) = a_i, ]

Here, for two strings \(S_1\) and \(S_2\), \(S_1S_2\) denotes their concatenation. For any string \(S\) of length \(l\), the quantity \(\operatorname{border}(S)\) is defined as the greatest positive integer \(k < l\) such that:

[ S_1 = S_{l-k+1},; S_2 = S_{l-k+2},; \dots,; S_k = S_l. ]

In addition, the following conditions must be met:

• Each string \(S_i\) is non-empty and contains only lowercase letters.
• The total length of all strings is at most \(2\times10^6\).

It is guaranteed that a solution exists.

Hint: One idea is to choose every string as a power string of the letter a (i.e. "a" repeated some number of times). In this case, if \(S_i = a^{L_i}\) and \(S_{i+1} = a^{L_{i+1}}\), then \(S_iS_{i+1} = a^{L_i+L_{i+1}}\) and its longest border is of length \(L_i+L_{i+1}-1\). Hence, one valid approach is to enforce the relation:

[ L_i + L_{i+1} - 1 = a_i, \quad 1\le i\le n. ]

This reduces the problem to finding positive integers \(L_1,L_2,\dots,L_{n+1}\) (with \(L_i\ge 1\)) satisfying the above equations and the total length constraint. One can then simply output \(S_i = a^{L_i}\) for each \(i\).

inputFormat

The first line contains an integer \(n\) (the length of the sequence). The second line contains \(n\) space-separated positive integers \(a_1,a_2,\dots,a_n\).

outputFormat

Output \(n+1\) lines, where the \(i\)-th line contains the string \(S_i\). These strings must satisfy: for each \(1\le i\le n\), \(\operatorname{border}(S_iS_{i+1}) = a_i\).

sample

1
1

a
a