eolymp
bolt
Try our new interface for solving problems
Problems

Поиск в словаре

Поиск в словаре

Time limit 2 seconds
Memory limit 256 MiB

Задан набор s_1, s_2, ..., s_n, состоящий из n строк словаря. Дополнительно задан набор q_1, q_2, ..., q_m, состоящий из m строк запросов.

Для каждой строки q_i найдите, сколько строк из словаря имеют префикс q_i. Более формально, для каждого индекса i, найдите количество таких индексов t, что q_i является префиксом s_t.

Input data

Первая строка содержит два целых числа n и m (1n, m10^5). Каждая из n следующих строк содержит непустую строку s_i. Каждая из m следующих строк содержит непустую строку q_i. Обратите внимание, что строки в наборе могут повторяться.

Output data

Выведите m целых чисел: i-тое число должно обозначать ответ для строки q_i.

Examples

Input example #1
3 3
aba
a
ba
a
b
bb
Output example #1
2
1
0
Author Геральд Агапов
Source Летняя школа Севастополь 2013, Волна 1, День 6