마법의 룬 패턴 찾기

에레브의 여제 시그너스는 마법의 힘을 더 강하게 만들기 위해 고대의 룬 조각들을 찾아내야 한다. 룬 조각들은 특정한 패턴을 이루고 있으며, 이 패턴을 해독하면 메이플 월드에 새로운 힘을 불어넣을 수 있다.

고대의 마법사들이 남긴 룬 조각들로 이루어진 긴 문자열 $T$가 있는데, 이 문자열은 오직 두 가지 마법 기호, a와 b로만 이루어져 있다. 이 기호들은 각각 고대 마법의 상징이며, 시그너스 기사단은 이 패턴을 해독해야 한다.

여러분의 임무는 룬 조각을 분석하여, 다음 조건을 만족하는 가장 긴 패턴 $P$를 찾아내는 것이다:

• 패턴 $P$는 a와 b로만 이루어진 문자열이다.
• 패턴 $P$, 또는 $P$의 기호를 모두 뒤바꾼 패턴 $P'$ (즉, a를 b로, b를 a로 바꾼 패턴)로 룬 조각 문자열 $T$를 덮을 수 있어야 한다.
  • 이때, 문자열 $T$의 연속한 부분문자열이 패턴과 일치할 때에만 그 부분을 패턴으로 덮을 수 있다.
  • 문자열 $T$의 모든 위치를 패턴 $P$, 또는 $P'$로 덮을 수 있어야 한다. 덮는 과정에서 겹치는 부분이 생겨도 좋다.
• 길이가 $K$ 보다 길지 않으면서 가장 길고 사전 순으로 가장 앞에 오는 패턴 $P$를 찾아야 한다.

예를 들어, 고대의 룬 조각 $T$가 aabbabbaab라면, aab와 bba 패턴을 한 글자씩 겹쳐서 덮을 수 있다. 또는 aabba와 bbaab라는 더 긴 패턴도 조건을 만족하는 것을 알 수 있다. 그러나 aabb와 bbaa 패턴으로는 $T$를 덮을 수 없다. 만약 $K$가 $3$ 또는 $4$라면, $P$는 aab가 되며, $K$가 $5$ 이상 $9$ 이하라면, $P$는 aabba가 된다.

고대 마법의 비밀을 풀고, 여제 시그너스를 도와 메이플 월드에 새로운 힘을 가져오자!

입력 형식

첫 줄에 문자열 $T$의 길이를 나타내는 정수 $N$과 패턴 $P$의 최대 길이를 나타내는 정수 $K$가 공백으로 구분되어 주어진다. ($K \le N \le 200\,000;$ $1 \le K \le 20$)

그다음 줄에 길이 $N$인 문자열 $T$가 주어진다. 문자열 $T$는 오직 a와 b로만 이루어져 있다.

출력 형식

첫 줄에 길이가 $K$ 보다 길지 않으면서 가장 길고 사전 순으로 가장 앞에 오는 패턴 $P$를 출력한다.

예제 1

10 9
aabbabbaab

aabba

예제 2

10 4
bbaabaabba

aab

예제 3

5 5
aabba

aabba

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설