Description

Fish is a fish that lives in the sea. One day he got bored and went treasure hunting. He found a palace deep on the seabed, but a gate with a combination lock blocked his way.

By consulting ancient books, Fish learned the following information about the password:

1. The length of the password is $N$.
2. The password contains only lowercase letters.
3. The lengths of the longest palindromic substrings centered at each character.
4. The lengths of the longest palindromic substrings centered between every pair of adjacent characters.

Fish soon realized that there might be infinitely many passwords that satisfy the conditions. After some analysis, he believes the lexicographically smallest one among them is most likely the answer. Can you help him find this password?

Note: For two strings $A$ and $B$, if their first $i$ characters are the same, and the $(i+1)$-th character of $A$ is smaller than that of $B$, then $A$ is said to be lexicographically smaller than $B$. For example, the string abc is lexicographically smaller than acb. If the lexicographic order of $A$ is smaller than that of all other passwords that satisfy the conditions, then $A$ is the lexicographically smallest one among them.

Input Format

The input consists of three lines. The first line contains a single integer $N$, the length of the password. The second line contains $N$ integers, giving the lengths of the longest palindromic substrings centered at each character. The third line contains $N-1$ integers, giving the lengths of the longest palindromic substrings centered between every pair of adjacent characters.

Output Format

Output a single line: the lexicographically smallest password that satisfies the conditions. The information from the ancient book is guaranteed to be correct, so there is always at least one valid password.

3
1 1 1
0 0

abc

3
1 3 1
0 0

aba

3
1 3 1
2 2

aaa

Hint

Constraints:

• For 20% of the testdata, $1 \le N \le 100$.
• For another 30% of the testdata, $1 \le N \le 1000$.
• For the remaining 50% of the testdata, $1 \le N \le 10^5$.

Translated by ChatGPT 5