Пошук у словнику

Задано набір 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.

Приклади