Поиск в словаре
Сложная
Ограничение по времени выполнения 2 секунды
Ограничение по использованию памяти 256 мегабайт
Задан набор s_1, s_2, ..., s_n, состоящий из n строк словаря. Дополнительно задан набор q_1, q_2, ..., q_m, состоящий из m строк запросов.
Для каждой строки q_i найдите, сколько строк из словаря имеют префикс q_i. Более формально, для каждого индекса i, найдите количество таких индексов t, что q_i является префиксом s_t.
Входные данные
Первая строка содержит два целых числа n и m (1 ≤ n, m ≤ 10^5). Каждая из n следующих строк содержит непустую строку s_i. Каждая из m следующих строк содержит непустую строку q_i. Обратите внимание, что строки в наборе могут повторяться.
Выходные данные
Выведите m целых чисел: i-тое число должно обозначать ответ для строки q_i.
Примеры
Ввод #1
Ответ #1
Отправки 256
Коэффициент принятия 3 %