Сопоставь меня, если сможешь
После просмотра фильма "Поймай меня, если сможешь" профессор Махаммад вдохновился на создание новой задачи для своих программистов. Поскольку некоторые процедуры в его исследованиях сильно зависят от сопоставления строк, он решил проверить навыки своих начинающих программистов в этой области. Задача проста: профессор дает вам строку и несколько запросов. Для каждой строки запроса необходимо подсчитать, сколько раз она встречается в строке, предоставленной профессором.
Входные данные
Первая строка входных данных содержит два положительных целых числа n (n ≤ 3000) и q, которые обозначают длину строки профессора и количество запросов соответственно. Вторая строка содержит строку профессора длиной n. Следующие q строк содержат строки запросов ненулевой длины.
Суммарная длина всех строк запросов не превышает 500000.
Выходные данные
Для каждого запроса выведите количество его вхождений в строку профессора.