题目描述

对于一个长度为 $n$、全由小写字母组成的的字符串，它有 $n$ 个后缀，把这些后缀按字典序排序，排名第 $i$ 的后缀的首字符在原串中的位置记作 $a_i$，那么 $a$ 就是原串的后缀数组。排名第 $i$ 和第 $i+1$ 的两个后缀的最长公共前缀长度记作 $h_i$，它通常被称作 Height 数组。

（注：本题的正解不需要知道怎么快速求后缀数组和 Height 数组，所以也用不上 SA 板子）

现在给你完整的后缀数组和一部分 Height 数组，你需要通过这些信息构造出原字符串。保证全由小写字母组成的原串存在。如果有多组解，输出字典序最小的一组。

输入格式

第一行一个整数 $n$，表示字符串的长度。

第二行 $n$ 个整数，第 $i$ 个是 $a_i$，表示原串的后缀数组。

第三行 $n-1$ 个整数，第 $i$ 个是 $h_i$，如果它不是 $-1$ 就代表 $h_i$ 的值，如果是 $-1$ 则代表 $h_i$ 未指定，真正的 $h_i$ 可以是任何数。

输出格式

输出一行一个长度为 $n$ 的字符串，表示字典序最小的满足要求的原串。

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

提示

• 对于 $20\%$ 的数据，$n\le 4$。
• 对于 $40\%$ 的数据，$n\le 20$。
• 对于另外 $20\%$ 的数据，$h$ 没有 $-1$。
• 对于另外 $20\%$ 的数据，$h$ 全为 $-1$。
• 对于全部数据，$1\le n\le 5000$。