LCC '21 Contest 4 J3 - Ben's Gaming Addiction

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Ben's favourite game is osu redtea!

The game is simple: given a 3 letter sequence s_i, output the longest word in the dictionary that contains s_i as a substring. The game is played for Q rounds with the same dictionary, which contains N words, none of which exceed 20 characters long.

Ben is, unfortunately, not great at the game, so he needs your help. Please write a program that will play the game for him!

Input Specification

The first line contains an integer representing the size of the dictionary, N (0 \le N \le 10^{4}).

The next N lines contain the words in the dictionary, consisting of lowercase alphabetic characters. None of the words will exceed 20 characters long.

The next line contains Q which represents the number of rounds being played Q (0 \le Q \le 10^{2}).

The next Q lines contain s_i, representing the 3 letter sequence. The letters will be lowercase alphabetic characters.

Output Specification

For each of the Q rounds, output the longest word containing the 3 letter sequence. If multiple valid words have the same length, output the lexicographically least word. If no valid word exists, output -1.

Sample Input 1

5
boxes
more
moreover
layman
foregoes
3
ore
aym
meo

Sample Output 1

foregoes
layman
-1

Comments

There are no comments at the moment.