Suffix reconstruction#5736
Given a text of length , we create its suffix array by taking all its suffixes:
and sorting them lexicographically. As a result, we get a sorted list of suffixes:
and we call the sequence p(1),\ p(2),\ \ldots,\ p(n) the suffix array of . For example, if s = abbaabab, the sorted list of all suffixes is:
and the suffix array is 4,\ 7,\ 5,\ 1,\ 8,\ 3,\ 6,\ 2.
It turns out that it is possible to construct this array in linear time. However, your task is completely different: given p(1),\ p(2),\ \ldots,\ p(n), you should check whether there exists at least one text consisting of lowercase letters of the English alphabet for which this sequence is the suffix array. If so, output any such text. Otherwise, output .
The input contains several descriptions of suffix arrays. The first line contains the number of descriptions (1 \le t \le 100). Each description begins with a line containing the length of both the text and the array (1 \le n \le 500\,000). The next line contains integers p(1),\ p(2),\ \ldots,\ p(n). You may assume that 1 \le p(i) \le n and each value appears exactly once in the array. The total input size will not exceed MB.
For each test case, output any text resulting in the given suffix array. If there is no such text consisting of lowercase letters of the English alphabet, output .
1-nji mysal