2738. Suffix reconstruction

单点时限: 10.0 sec

内存限制: 256 MB

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 call the sequence the suffix array of . For example, if , the sorted list of all suffixes becomes:

and the suffix array is .

It turns out that it is possible to construct this array in a linear time. Your task will be completely different, though: given you should check if there exist 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 (). Each description begins with a line containing the length of both the text and the array (). Next line contains integers . You may assume that and no value of occurs twice. Total size of the input will not exceed 50MB.

输出格式

For each test case output any text resulting in the given suffix array. In case there is no such text consisting of lowercase letters of the English alphabet, output .

If there are multiple answers, output the smallest dictionary order in the given suffix array.

样例

Input
6
2
1 2
2
2 1
3
2 3 1
6
3 4 5 1 2 6
14
3 10 2 12 14 5 13 4 1 8 6 11 7 9
7
5 1 7 4 3 2 6
Output
ab
aa
bab
suffix
reconstruction
issofun

4 人解决,6 人已尝试。

6 份提交通过,共有 9 份提交。

7.3 EMB 奖励。

创建: 10 年,3 月前.

修改: 2 年前.

最后提交: 1 年,11 月前.

来源: Central European Programming Contest 2008

题目标签