Madam Alola has been writing award-winning novels for many years but recently the popularity of her novels have started to decline. When she read the comments by the critics, she was shocked to hear that they found her sentences plain and boring. In order to make her stories more interesting, she embarked on research to find the most interesting sentences and she found that the most interesting sentences were palindromes.
Palindromes are sentences where if you reverse the order of the letters in the sentence, the new sentence is exactly the same as the old one. For simplicity we will ignore non-alphanumeric characters and case sensitivity. For example, the sentence "Madam, I'm Adam" is a valid palindrome.
Her research also tells her that sentences with only alphanumeric characters are boring and she wants to make her sentences more interesting by having as many non-alphanumberic characters in the sentence as possible. For example, "Madam, I'm Adam", is much more interesting that "Madam Im Adam".
Your job is to help her find the most interesting sentence with exactly L alphanumeric characters from a passage so she can mimic(no plagiarism :P) the sentence for her own novel. If no such sentence exists, print a blank line.
The first line of input contains the passage
The second line of input contains an integer Q representing the number of queries.
The following Q lines contain one integer each representing the query L
Output all of the most interesting sentences in each passages in the same order as it appears in the passage. Separate the answers to each query by a blank line. The sentence should start and end with an alphanumeric character.
The output is guaranteed to be sufficiently small
For all test cases, L will not exceed the number of alphanumeric characters in the passage
Subtask 1 (0%): Sample
Subtask 2 (4%): Q=1, 0 < L ≤ 10, passage contains at most 100 characters and only alphanumeric characters
Subtask 3 (7%): Q=1, 0 < L ≤ 1000, passage contains at most 1000 characters and only alphanumeric characters
Subtask 4 (13%): 0 < Q ≤ 1000, 0 < L ≤ 1000, passage contains at most 1000 and only alphanumeric characters
Subtask 5 (9%): Q=1, 0 < L ≤ 10, passage contains at most 1000 characters
Subtask 6 (17%): 0 < Q ≤ 10, 0 < L ≤ 50, passage contains at most 10000 characters and at most 1000 alphanumeric characters
Subtask 7 (21%): 0 < Q ≤ 100, 0 < L ≤ 75, passage contains at most 100000 characters and at most 10000 alphanumeric characters
Subtask 8 (29%): 0 < Q ≤ 1000, 0 < L ≤ 100, passage contains at most 1000000 characters and at most 100000 alphanumeric characters
ab 3 1 2 1
a b a b
Helloo Madam, I'm Adam. Good bye. 3 11 2 5
Madam, I'm Adam ll oo oo am, I'm A
| Subtask | Score |
|---|---|
| 1 | 0 |
| 2 | 4 |
| 3 | 7 |
| 4 | 13 |
| 5 | 9 |
| 6 | 17 |
| 7 | 21 |
| 8 | 29 |