Lexicographically Smallest Password

Fish, a curious sea creature, finds a secret palace guarded by a door with a password lock. By studying ancient texts, Fish learns that the password must satisfy the following properties:

• The password is of length \(N\).
• It consists only of lowercase letters.
• For each character (at index \(i\), 0-indexed here), if you consider it as the center of an odd–length palindrome, the maximum palindrome length is given by an integer \(A_i\). That is, if \(A_i=2r+1\), then for every \(j=0,1,\ldots,r\), the condition \(S[i-j] = S[i+j]\) must hold. Moreover, if both indices \(i-r-1\) and \(i+r+1\) exist, then \(S[i-r-1]\) and \(S[i+r+1]\) must differ (so that the palindrome centered at \(i\) is maximum).
• For each gap between adjacent characters (i.e. between index \(i\) and \(i+1\)), an even–length palindrome is considered. The maximum palindrome length for that gap is given by an even integer \(B_i\). If \(B_i = 2r\) (with possibly \(r=0\)), then for every \(j=0,1,\ldots,r-1\) (if \(r>0\)) we have \(S[i-j] = S[i+1+j]\). When \(B_i = 0\) it means that the two adjacent characters \(S[i]\) and \(S[i+1]\) are different. If both indices \(i-r\) and \(i+1+r\) exist (for \(r>0\)), then \(S[i-r]\) and \(S[i+1+r]\) must differ.

There may be many strings satisfying these conditions. However, among all valid passwords, Fish believes that the lexicographically smallest one is the true answer. Two strings are compared in lexicographical order: For the first index where they differ, the string with the smaller character is considered smaller. For example, "abc" is lexicographically smaller than "acb".

Your task is to help Fish determine the lexicographically smallest password that satisfies all the conditions.

Note: The input guarantees that there is at least one valid solution.

inputFormat

The input consists of three lines:

1. The first line contains an integer \(N\) \((1 \leq N \leq 10^5)\) indicating the length of the password.
2. The second line contains \(N\) space–separated positive odd integers: \(A_0, A_1, \ldots, A_{N-1}\), where \(A_i\) represents the maximum odd–length palindrome centered at index \(i\). It is guaranteed that \(A_i \leq N\) and \(A_i\) is odd.
3. The third line contains \(N-1\) space–separated nonnegative even integers: \(B_0, B_1, \ldots, B_{N-2}\), where \(B_i\) represents the maximum even–length palindrome centered in the gap between indices \(i\) and \(i+1\). It is guaranteed that \(B_i \leq N\) and \(B_i\) is even.

outputFormat

Output a single line containing the lexicographically smallest password (a string of lowercase letters) that satisfies all the given conditions.

sample

5
1 1 1 1 1
0 0 0 0

ababa