One day Sohom was playing an indie game. Before the final boss, he found a Magical Chest and a paper. The Chest contains some armor and sword which will make it easier to defeat the boss using them. It requires a passcode to open. The instruction to get the passcode is written on the paper. The paper goes like this,
You will be given a string S of length N, and a value K. You need to find a substring of length K from the given string S such that its characters can be rearranged to make a palindrome.
For example, the string “abab” can be rearranged to make strings “aabb“, “baab”, “abab”, “abba” etc. Among them “abba”, “baab” are palindrome, and “abba” is lexicographically smaller. A string is a palindrome if it reads the same forward and backward.
If there are several possible substrings that can be rearranged to make a palindrome, print the lexicographically smaller one. String A is lexicographically smaller than String B, if A is a prefix of B or for smallest index, $i$ where $A[i]!=B[i]$, $A[i]<B[i]$.
Note that, rearranging doesn't change the order of characters in the original string.
After an intense battle in the previous round, Sohom is now too tired to solve the passcode. Now he asks for your help. Help him to get the passcode or say that there is no such passcode.
The first line of input contains N, K, and the second line contains S.
$1 <= K <= N <= 10^6$
S contains lowercase alphabets only
If there is no suitable palindrome of length K, print “No Passcode Found“ (without quotes). Otherwise print the lexicographically smaller palindrome(after rearranging) in a single line.
Input | Output |
---|---|
6 3 acbaac | aba |
Among all substrings of length 3, substring “baa” from index 2-4 (0-indexed) and substring “aac” from index 3-5 can be rearranged to make palindromes “aba” and “aca” respectively. Among them “aba” is lexicographically smaller. |
Input | Output |
---|---|
8 4 abcdefgh | No Passcode Found |