Запросы на наибольший общий суффикс
(Рэп-баттл)
Вам дан список из
n различных слов: , а также список из q слов-запросов . Ваша задача — найти лексикографически наименьшее слово из списка a, которое отличается от w и при этом имеет с ним самый длинный общий суффикс.Входные данные
Первая строка входных данных содержит одно целое число
n (2 ≤ n ≤ 25 000), обозначающее количество строк в списке.В следующих
n строках записаны слова. Каждое слово состоит из строчных английских букв, а длина любого слова не превышает 30 символов.Следующая строка содержит одно целое число
q (1 ≤ q ≤ 25 000), обозначающее количество запросов.Далее идут
q строк, каждая из которых содержит слово-запрос.Каждое слово состоит из строчных английских букв, а его длина не превышает 30 символов.
Выходные данные
Для каждого запроса выведите в отдельной строке лексикографически наименьшее слово из списка, которое отличается от слова-запроса и имеет с ним наибольший общий суффикс.
Примеры
Input | Входные данные |
4
perfect
rhyme
crime
time
2
crime
rhyme | 4
perfect
rhyme
crime
time
2
crime
rhyme |
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB