사전순 최소 문자열

면접 대비

시간 제한0.5초메모리 제한1024 MB

요약

문자열 S와 정수 K가 주어졌을 때, S_i와 S_(i+K)를 자유롭게 교환해 만들 수 있는 사전순으로 가장 작은 문자열을 구합니다.

난이도: 쉬움10점 중 3점
유형: 문자열, 정렬, 구현
정답자: 아직 제출이 없습니다

문제

Lexicoville 마을에 사는 릴리와 이단에게 정체불명의 편지가 도착했다. 편지에는 정수 $K$ 와 소문자로만 이루어진 문자열 $S$ 가 주어지는 수수께끼가 적혀 있다. 마을 사람들은 언제든지 인덱스 $i$ 를 골라 $S_i$ 와 $S_{i+K}$ 의 문자를 서로 바꿀 수 있다. 이 연산만을 사용해 만들 수 있는 문자열 중 사전순으로 가장 앞서는 문자열을 구하라.

입력

첫 번째 줄에 문자열 $S$ 가 주어진다( $1 \le |S| \le 10^5$ ). 두 번째 줄에 정수 $K$ 가 주어진다( $1 \le K < |S|$ ).

출력

만들 수 있는 문자열 중 사전순으로 가장 앞서는 문자열을 한 줄에 출력한다.

예제2

예제 1
입력
```
zaaab
4
```
예상 출력
```
baaaz
```
예제 2
입력
```
njoab
2
```
예상 출력
```
banjo
```