P1124 File Compression

提高文件的压缩率一直是人们追求的目标。近几年有人提出了这样一种算法，它虽然只是单纯地对文件进行重排，本身并不压缩文件，但是经这种算法调整后的文件在大多数情况下都能获得比原来更大的压缩率。

The algorithm is as follows: For a string $S$ of length $n$, first construct $n$ strings, where the $i$-th string is obtained by moving the first $i-1$ characters of $S$ to the end. Then sort these $n$ strings by their first character in ascending order; if two strings have the same first character, sort them by their positions in $S$ in ascending order. The last characters of the sorted strings form a new string $S'$, whose length is also $n$ and which contains every character of $S$. Finally, output $S'$ and the position $p$ of the first character of $S$ in $S'$. Example: $S$ is `example`. 1. Construct $n$ strings. ```plain example xamplee ampleex mpleexa pleexam leexamp eexampl ``` 2. Sort the strings. ```plain ampleex example eexampl leexamp mpleexa pleexam xamplee ``` 3. Compression result. $S' = \texttt{xelpame}$，$p = 7$。 Because of the characteristics of English words, certain letters occur very frequently, so identical letters are very likely to be grouped together in $S'$, which improves the compression ratio of $S'$. Although this algorithm leverages properties of English words, in practice it is found to work for almost all file compression. Write a program that reads $S'$ and $p$, and outputs the string $S$. It is guaranteed that $S$ contains only lowercase letters (so the input $S'$ also contains only lowercase letters).

Three lines in total. The first line contains an integer $n$ ($1 \le n \le 10000$), the length of $S'$. The second line contains the string $S'$. The third line contains an integer $p$.

One line, the string $S$.

Translated by ChatGPT 5