Moo Time Candidates

Farmer John loves the USACO contests, especially the part when Bessie exclaims, "Now is Moo Time" and moos throughout the contest. He defines the contest as a text string S of length \(N\) (\(3\le N\le 20000\)) consisting of lowercase letters. A moo is defined as a substring of the form \(c_i c_j c_j\) (with indices consecutive) where \(c_i\) and \(c_j\) are characters and \(c_i\neq c_j\). However, if some moo appears at least \(F\) times (\(1\le F\le N\)) then it is likely to be from Bessie.

There is one more twist. Farmer John's downloaded contest file might be corrupted – it may differ from the original in at most one character. Taking this into account, determine all candidate moos (of the form \(xyy\) with \(x\neq y\)) for which there exists an original string (with Hamming distance at most 1 from the given string) in which the moo appears at least \(F\) times. Output the valid candidate moo strings in lexicographical order.

Note: When no error is applied (i.e. the downloaded file is correct) the number of appearances is the exact count of occurrences of the substring in the file. When an error is applied (exactly one character change in the file) the error might destroy some occurrences already present or create new ones. In particular, if an occurrence straddles the error position then it can be fixed only if in the unaffected positions the letters match the candidate and you can change the error position to the required letter (which must be different from the letter in the downloaded file).

Formally, for a candidate moo string \(p=xyy\) (with \(x\neq y\)), let the baseline occurrence count be the number of indices \(i\) (\(0\le i\le N-3\)) such that \(S[i]=x\), \(S[i+1]=y\), and \(S[i+2]=y\). Also, if you change a character at some position \(j\) (and only that position) from \(S[j]\) to some letter \(L\) (with \(L\neq S[j]\)), then for each affected substring starting at \(i\) with \(j\in\{i,i+1,i+2\}\) you obtain a moo occurrence if and only if for every position \(k\in\{0,1,2\}\) with \(k\neq j-i\) the letter remains the same as in \(S\) and equals \(p[k]\), and furthermore \(L=p[j-i]\) (note that this change must be different from the original \(S[j]\)). Your task is to decide for each candidate \(xyy\) whether it is possible that the original (possibly corrected) file contains at least \(F\) occurrences of \(xyy\). If yes, output it.

inputFormat

The first line contains two integers \(N\) and \(F\) separated by a space.

The second line contains a string \(S\) of length \(N\) consisting of lowercase letters.

outputFormat

Output all candidate moo strings (of the form xyy with \(x\neq y\)) for which there exists a possible original string (differing from \(S\) in at most one position) that contains at least \(F\) occurrences of that candidate. Each candidate should be printed on a separate line in lexicographical order. If no candidate qualifies, output nothing.

sample

6 2
moomoo

moo