29768번 - 팰린드롬 이름

팰린드롬의 마법사 엣지는 오늘도 팰린드롬을 찾고 있었다. 그러던 도중 팰린드롬을 좋아하는 사람들이 모이는 축제를 만들고 싶어졌다. 축제의 이름의 길이는 $N$이고 이름은 서로 다른 영어 알파벳 소문자 $K$가지로 이루어져 있어야 한다. 마법사 엣지는 축제 이름의 조건을 만족하면서 서로 다른 부분 문자열 중 팰린드롬의 개수가 가장 많은 문자열을 축제의 이름으로 정한다. 문제에 사용된 단어의 의미는 예제 아래에 위치한 노트를 참고하자.

마법사 엣지를 위해 축제의 이름을 하나 만들어주자. 축제의 이름으로 정할 수 있는 이름이 여러 개라면, 사전순으로 가장 앞선 이름을 만든다.

첫째 줄에 이름의 길이 $N$과 알파벳 소문자의 개수 $K$가 공백으로 구분되어 입력된다. $(1≤N≤100\,000, 1≤K≤26, K≤N)$

첫째 줄에 마법사 엣지가 정할 축제의 이름을 출력한다.

팰린드롬은 앞으로 읽으나 뒤로 읽으나 똑같은 문자열을 말한다. 예를 들어 level은 팰린드롬이지만, apple은 아니다.

부분 문자열이란 문자열에서 연속한 문자 몇 개를 이어 붙인 문자열을 뜻한다. 예를 들어 aba의 부분 문자열은 a, b, a, ab, ba, aba가 있다.

두 부분 문자열 $A$, $B$가 서로 다르다는건 두 부분 문자열의 길이가 다르거나, $A$의 $i$번째 글자와 $B$의 $i$번째 글자가 다르게 하는 어떤 $i$가 존재함을 뜻한다. 서로 다른 부분 문자열이란 부분 문자열 중 서로 다른 것들이다. 예를 들어 aba의 서로 다른 부분 문자열은 a, b, ab, ba, aba이다.

사전순은 사전에 쓰이는 문자열의 배열 순서를 말한다. 예를 들어 abc는 acb보다 사전순으로 앞섰고, aa는 aaa보다 사전순으로 앞섰다.