진화하는 어원학

Eelco는 최근 단어의 기원을 연구하는 어원학에 관심을 갖게 되었다. 그는 특히 단어가 시간에 따라 변하는 방식을 좋아한다. 발음이 바뀌고, 다른 언어에서 단어를 빌려 오고, 문화에 따라 의미가 달라진다. Eelco는 처음으로 Networking With Etymologists: Revolutionary Conference에 참석한다. 좋은 첫인상을 남기려고 기존 단어로 새 단어를 만드는 새로운 방법을 발표할 계획이다.

기존 단어 $s$로 새 단어를 만들려면 $s+s$의 글자를 첫 글자부터 시작해 두 글자마다 하나씩 취한다. 예를 들어 etymology에 이 방법을 적용하면 eyooytmlg가 된다. 이 과정은 여러 번 반복할 수 있다. Eelco는 학회에서 쓸 새 단어 목록이 필요해서, 정해진 횟수만큼 이 방법을 적용하는 프로그램을 작성하고 있다.

첫째 줄에 두 정수 $n$과 $k$($1 \leq n \leq 10^5$, $1 \leq k \leq 10^{18}$)가 주어진다. $n$은 원래 단어의 길이이고, $k$는 방법을 적용하는 횟수이다.

둘째 줄에는 길이가 $n$인 문자열 $s$가 주어진다. $s$는 영어 소문자(a-z)로만 이루어진 원래 단어이다.

원래 단어에 이 방법을 $k$번 적용한 결과 단어를 출력한다.