HACKING - Hacking

A coach of one of the soccer world finals teams (lets call him Hugo Hacker) wants to find out secret information about an opposing team before the game. The coach of the opposing team has a website with public information about his team. Hugo suspects that also secret information is stored on the computer which hosts the website.

The website contains a form which allows to search for key words and returns a chunk of a text file which contains the key word. Hugo has found out that by entering words which cannot be found in the documents publicly available, he can exploit a bug in the search and get access to other files on the computer. He already knows the publicly available documents. However the search box has a restriction on the maximum length of a word and the characters which can be entered. Can you tell him a word which can be entered in the search box and which does not occur as a substring in the documents?

Input

The first line of the input consists of the number of test cases which are to follow. Each test case consists of two lines: in the first line there are three integers n (1 ≤ n ≤ 10000), m (1 ≤ m ≤ 100) and k (1 ≤ k ≤ 26), where n is the length of the publicly available documents, m is the maximum allowed length of words which can be entered in the search box, and k specifies that the search box allows only the first k characters of the alphabet. The second line of each test case describes the publicly available documents and consists of n lower-case letters.

Output

For each test case in the input, print one line in the output containing a word which does not occur as a substring in the given text. The word should have at most m lower-case characters from the first k letters in the alphabet. You may assume that for each given test case, there is always at least one such word (you may print any such word).

Example

Input:
2
9 3 2
bbbaababb
9 3 2
aaabbabaa

Output:
aaa
bbb

Added by:Adrian Kuegel
Date:2010-06-21
Time limit:0.402s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:German Collegiate Programming Contest 2010 (Authors: Simon Gog/Adrian Kuegel)

hide comments
2021-08-12 09:33:21
using hash , time 0,39sss
2015-07-03 18:23:28 Pinku Deb Nath
Hello :) I used Trie(of substrings of length m) + BFS to find the first non-existing substring and I am getting tle, probably on the first test case. I figure that the complexity of building the trie is O(n*m) and bfs is maybe O(n*m + n*m). Is my idea r8? And is there any better algorithm to solve this?
2014-08-24 18:43:33 .:: Jarv1s ::.
Hi Adrian, I'm getting TLE for submission id 12226156. Can you help me figuring out the test cases please. I believe that I'm using a fast algorithm, but still no hope!
2013-03-03 08:12:10 iamthewalrus
Getting TLE for O(m(n+k))! :(
2011-05-16 11:05:59 Adrian Kuegel
it means that only letters from 'a' to 'a'+k-1 can be used
2011-05-14 04:41:51 Castiel
what exactly is k???? please explain.

Last edit: 2011-05-14 04:42:29
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.