Cyclic Rotation Cipher

For some time the police have been intercepting encrypted messages from a criminal group, but they have been unable to decrypt them. During a recent raid of an abandoned warehouse they seized the encryption device, and careful analysis revealed how it works.

The device takes plain text as input. The text is first converted to lowercase and stripped of everything except the Latin letters a … z, producing a string $S = s_1 s_2 \dots s_n$. Then all $n$ cyclic rotations of $S$ (call them $S_1 \dots S_n$, where $S_i = s_i \dots s_n s_1 \dots s_{i-1}$) are sorted lexicographically. The encrypted message consists of the index $i$ of the original string among the sorted rotations, together with a string $R$ formed by taking the last letter of every rotation, read in sorted order.

For example, abracadabra is encoded as 3 rdarcaaaabb:

 1. aabracadabr = S11
 2. abraabracad = S8
 3. abracadabra = S1
 4. acadabraabr = S4
 5. adabraabrac = S6
 6. braabracada = S9
 7. bracadabraa = S2
 8. cadabraabra = S5
 9. dabraabraca = S7
10. raabracadab = S10
11. racadabraab = S3

The sorted rotations are numbered $1$ to $11$; the third one is the original string, so $i = 3$, and reading the last letter of each rotation from top to bottom gives rdarcaaaabb.

Given an encrypted message $(i, R)$, recover the original string $S$. The messages can be very long, so your program must be efficient.

The first line contains the index $i$ ($1 \le i \le n$). The second line contains the string $R$ of length $n$ ($1 \le n \le 1\,000\,000$). The original message $S$ is guaranteed to exist and to be unique.

Print the string $S$ on a single line.