Дистанционный практикум по программированию

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

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

Требуется написать программу, которая по заданному числу n, n словам словаря
t₁, t₂, …, t_n, заданному числу m и m строкам-образцам s₁, s₂, …, s_m вычислит для каждой строки-образца количество слов из словаря, для которых эта строка-образец  является супрефиксом.

Формат входного файла

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

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

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

Последующие m строк содержат строки-образцы s₁, s₂, …, s_m, по одной на каждой строке. Каждая строка-образец состоит из строчных букв латинского алфавита: Длина каждой строки-образца не превышает 50. Суммарная длина всех строк-образцов не превышает 10⁶. Никакая строка-образец не является пустой строкой.

Формат выходного файла

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

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

Пример входного и выходного файлов

стандартный ввод	стандартный вывод
4 abacaba abracadabra aa abra 3 a abra abac	4 2 0