Задачі
Пошук у словнику
Пошук у словнику
Задано набір \textbf{s_1}, \textbf{s_2}, ..., \textbf{s_n}, який складається з \textbf{n} рядків словника. Додадтково задано набір \textbf{q_1}, \textbf{q_2}, ..., \textbf{q_m}, який складається з \textbf{m} рядків запитів.
Для кожного рядка \textbf{q_i} знайдіть, скільки рядків зі словника мають префікс \textbf{q_i}. Більш формально, для кожного індекса \textbf{i}, знайдіть кількість таких індексів \textbf{t}, що \textbf{q_i} є префіксом \textbf{s_t}.
\InputFile
Перший рядок містить два цілих числа \textbf{n} та \textbf{m} (\textbf{1} ≤ \textbf{n}, \textbf{m} ≤ \textbf{10^5}). Кожен з \textbf{n} наступних рядків містить непорожній рядок \textbf{s_i}. Кожен з \textbf{m} наступних рядків містить непорожній рядок \textbf{q_i}. Зверніть увагу, що рядки у наборі можуть повторюватись.
\OutputFile
Виведіть \textbf{m} цілих чисел: \textbf{i}-те число повинно означати відповідь для рядка \textbf{q_i}.
Вхідні дані #1
3 3 aba a ba a b bb
Вихідні дані #1
2 1 0