순환 회전 암호

경찰은 한동안 어느 범죄 조직이 주고받는 암호문을 가로채 왔지만, 이를 해독하지 못하고 있었다. 최근 한 급습 작전에서 경찰은 암호화 장치를 압수했고, 정밀 분석을 통해 그 작동 원리를 밝혀냈다.

이 장치는 평문을 입력으로 받는다. 먼저 평문을 모두 소문자로 바꾸고 라틴 문자 a … z 를 제외한 모든 문자를 제거하여 문자열 $S = s_1 s_2 \dots s_n$ 을 만든다. 그런 다음 $S$ 의 모든 순환 회전 $S_1 \dots S_n$ (여기서 $S_i = s_i \dots s_n s_1 \dots s_{i-1}$) 을 사전순으로 정렬한다. 암호문은 정렬된 회전들 중 원래 문자열 $S$ 가 놓인 위치의 번호 $i$ 와, 정렬된 순서대로 각 회전의 마지막 글자를 모아 만든 문자열 $R$ 로 이루어진다.

예를 들어 abracadabra 는 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

정렬된 회전에는 $1$ 부터 $11$ 까지 번호가 매겨져 있고, 세 번째 회전이 원래 문자열이므로 $i = 3$ 이다. 각 회전의 마지막 글자를 위에서 아래로 읽으면 rdarcaaaabb 가 된다.

암호문 $(i, R)$ 이 주어졌을 때 원래 문자열 $S$ 를 복원하라. 메시지가 매우 길 수 있으므로 프로그램은 효율적으로 동작해야 한다.

첫째 줄에 번호 $i$ ($1 \le i \le n$) 가 주어진다. 둘째 줄에 길이가 $n$ 인 문자열 $R$ ($1 \le n \le 1\,000\,000$) 이 주어진다. 원래 문자열 $S$ 는 반드시 존재하며 유일함이 보장된다.

원래 문자열 $S$ 를 한 줄에 출력한다.