“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 ≤ i ≤ min(|x|,|y|)), that $x_i < y_i$, and for any j (1 ≤ j < i), $x_j = y_j$. Here |a| denotes the length of the string a. The lexicographic comparison of strings is implemented by operator < in modern programming languages. For example, everybody is lexicographically smaller than somebody.
Let suf i be $x_ix_{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 ≤ i ≤ n) is the starting position of the i-th lexicographically smallest suffix sufj, which means $sa_i$ = j. And $height_i$ (2 ≤ i ≤ n) is the length of longest common prefix between suf $sa_{i-1}$ and suf $sa_i$. For example, the sa and height for remember is {6,4,2,7,5,3,8,1} and {0,2,1,0,1,0,1} 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.