407501: GYM102803 E Everybody Lost Somebody

"But there's nothing I wouldn't do to wake up and remember it."

Jonathan is fan of string problems. He is learning lexicographic order and suffix array these days.

String $$$x$$$ is lexicographically less than string $$$y$$$, if either $$$x$$$ is a prefix of $$$y$$$ (and $$$x \neq y$$$), or there exists such $$$i ~ (1 \leq i \leq \min(|x|, |y|))$$$, that $$$x_i < y_i$$$, and for any $$$j ~ (1 \leq j < i)$$$, $$$x_j = y_j$$$. Here $$$|a|$$$ denotes the length of the string $$$a$$$. The lexicographic comparison of strings is implemented by operator $$$\texttt{<}$$$ in modern programming languages. For example, everybody is lexicographically smaller than somebody.

Let $$$\operatorname{suf} i$$$ be $$$x_i x_{i+1} \cdots x_n$$$ for string $$$x$$$ of length $$$n$$$. In suffix array problems, there are two commonly used arrays: $$$sa$$$ of length $$$n$$$ and $$$height$$$ of length $$$n-1$$$. Formally, $$$sa_i ~ (1 \leq i \leq n)$$$ is the starting position of the $$$i$$$-th lexicographically smallest suffix $$$\operatorname{suf} j$$$, which means $$$sa_i = j$$$. And $$$height_i ~ (2 \leq i \leq n)$$$ is the length of longest common prefix between $$$\operatorname{suf} sa_{i-1}$$$ and $$$\operatorname{suf} sa_i$$$. For example, the $$$sa$$$ and $$$height$$$ for remember is $$$\lbrace6,4,2,7,5,3,8,1\rbrace$$$ and $$$\lbrace0,2,1,0,1,0,1\rbrace$$$ respectively.

As we all know, Little Y is a Riddler. One day, Little Y got a string $$$S$$$ of length $$$n$$$ consisting of only lowercase letters. He used suffix-array algorithms to get the array $$$sa$$$ and $$$height$$$. He erased several numbers in $$$height$$$ and gave the two modified array to Jonathan.

Curiously, Jonathan wants to know what the string $$$S$$$ is. Please help him to figure out a possible answer. Since there may be multiple answers, you only need to print the lexicographically smallest one. It is guaranteed that the answer exists.

The first line contains one integer $$$n ~ (1 \leq n \leq 5000)$$$, indicating the length of the string $$$S$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$, indicating the array $$$sa$$$.

The third line contains $$$n-1$$$ integers $$$b_2, b_3, ..., b_n$$$, indicating the modified array $$$height$$$. $$$b_i = -1$$$ means that $$$height_i$$$ is erased by Little Y. Otherwise, $$$height_i = b_i$$$.

One line with one string $$$S$$$ of length $$$n$$$, indicating the lexicographically smallest answer.

4
4 1 2 3
1 0 0

abca

4
4 1 2 3
1 -1 0

aaba

11
11 4 8 1 5 9 2 6 10 3 7
-1 -1 -1 0 -1 -1 -1 0 -1 3

abcabbcabca