Рабочее место участника

Строка `s` называется супрефиксом для строки `t`, если `t` начинается с `s` и заканчивается на `s`. Например, «abra» является супрефиксом для строки «abracadabra». В частности, сама строка `t` является своим супрефиксом. Супрефиксы играют важную роль в различных алгоритмах на строках.

В этой задаче требуется решить обратную задачу о поиске супрефикса, которая заключается в следующем. Задан словарь, содержащий `n` слов `t_1,\ t_2,\ …,\ t_n` и набор из `m` строк-образцов `s_1,\ s_2,\ …,\ s_m`. Необходимо для каждой строки-образца из заданного набора найти количество слов в словаре, для которых эта строка-образец является супрефиксом.

Требуется написать программу, которая по заданному числу `n`, `n` словам словаря `t_1,\ t_2, …,\ t_n`, заданному числу `m` и `m` строкам-образцам `s_1,\ s_2,\ …,\ s_m` вычислит для каждой строки-образца количество слов из словаря, для которых эта строка-образец является супрефиксом.

Первая строка входного файла содержит целое число `n` (`1 ≤ n ≤ 200 000`).

Последующие `n` строк содержат слова `t_1,\ t_2,\ …,\ t_n`, по одному слову в каждой строке. Каждое слово состоит из строчных букв латинского алфавита. Длина каждого слова не превышает 50. Суммарная длина всех слов не превышает `10^6`. Словарь не содержит пустых слов.

Затем следует строка, содержащая целое число `m` (`1 ≤ m ≤ 200 000`).

Последующие `m` строк содержат строки-образцы `s_1,\ s_2,\ …,\ s_m`, по одной на каждой строке. Каждая строка-образец состоит из строчных букв латинского алфавита. Длина каждой строки-образца не превышает 50. Суммарная длина всех строк-образцов не превышает `10^6`. Никакая строка-образец не является пустой строкой.

Выходной файл должен содержать `m` чисел, по одному на строке.

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

4
abacaba
abracadabra
aa
abra
3
a
abra
abac

4
2
0