Запросы на наибольший общий суффикс

(Рэп-баттл)

Вам дан список из n различных слов: , а также список из q слов-запросов . Ваша задача — найти лексикографически наименьшее слово из списка a, которое отличается от w и при этом имеет с ним самый длинный общий суффикс.

Входные данные

Первая строка входных данных содержит одно целое число n (2 ≤ n ≤ 25 000), обозначающее количество строк в списке.

В следующих n строках записаны слова. Каждое слово состоит из строчных английских букв, а длина любого слова не превышает 30 символов.

Следующая строка содержит одно целое число q (1 ≤ q ≤ 25 000), обозначающее количество запросов.

Далее идут q строк, каждая из которых содержит слово-запрос.

Каждое слово состоит из строчных английских букв, а его длина не превышает 30 символов.

Выходные данные

Для каждого запроса выведите в отдельной строке лексикографически наименьшее слово из списка, которое отличается от слова-запроса и имеет с ним наибольший общий суффикс.

Примеры