Ashton appeared for a job interview and is asked the following question. Arrange all the distinct substrings of a given string in lexicographical order and concatenate them. Print the character of the concatenated string. It is assured that given value of will be valid i.e. there will be a character. Can you help Ashton out with this?
For example, given the string , its distinct substrings are . Sorted and concatenated, they make the string . If then, the answer is , the character of the 1-indexed concatenated string.
Note We have distinct substrings here, i.e. if string is aa, it's distinct substrings are a and aa.
Complete the ashtonString function in the editor below. It should return the character from the concatenated string, 1-based indexing.
ashtonString has the following parameters:
- s: a string
- k: an integer
The first line will contain an integer , the number of test cases.
Each of the subsequent pairs of lines is as follows:
- The first line of each test case contains a string, .
- The second line contains an integer, .
Each character of string
will be an appropriate integer.
Print the character (1-based index) of the concatenation of the ordered distinct substrings of .
The substrings when arranged in lexicographic order are as follows