Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Living on a Prayer

By Zeronfinity · Limits 3s, 512 MB

Tommy is an unlucky guy who used to work on the docks. He and his wife Gina are not financially stable, so life is very tough for them. And since there is a strike that has made the docks become closed, Tommy has no work to do and has started spending more time at home. Gina tries to keep Tommy busy at home so that Tommy doesn’t feel upset. For that purpose, each day, Gina gives Tommy a string S and asks him to find the K-th palindromic sub-string of that string.

Tommy is too upset to play the game, but he doesn’t want to break Gina’s heart either, as they have got to hold on to what they’ve got, no matter how hard life’s been. So Tommy came to you, a brilliant problem solver. Your task is to find Tommy’s answers for each day, so that Gina’s heart doesn’t break.

Input

Input starts with an integer T, the number of days you have to help Tommy.

Each of the following T lines contains a string S and an integer K separated by space, Gina’s question for that day.

Constraints:
1 ≤ T ≤ 100
For any day,
1 ≤ Length of S ≤ 104
1 ≤ K ≤ 108

All the strings in the input consist of uppercase Latin letters only (A to Z).

Output

For each day, print the K-th lexicographically smallest palindromic substring of string S in a single line.

If such a substring does not exist, print -1 instead of the substring.

Sample

InputOutput
6
BDROCKS 3 
AA 1
AA 2
AA 3
AA 4
ABACABA 7
D
A
A
AA
-1
ABACABA

In the first string of the input, the palindromic substrings are “B”, “D”, “R”, “O”, “C”, “K”, “S”. The 3rd palindromic substring in lexicographical order is “D”.

In the second string of the input, the palindromic substrings are “A”, “A”, “AA”. The 1st palindromic substring in lexicographical order is “A”, the 2nd one is also “A”, the 3rd one is “AA” and the 4th one does not exist thus “-1” is printed in output.


A substring is a contiguous sequence of characters within a string. For example, “bc” is a substring of the string “abcda”. Two substrings are considered different if they either start at or end at different positions in the string, even if their contents are the same.


Discussion
Statistics

88% Solution Ratio

SMAN2901Earliest, 2w ago

solaimanopeFastest, 0.3s

shefinLightest, 2.1 MB

SMAN2901Shortest, 3559B

Submit

Login to submit