Сколько раз строка S встретится на промежутке [l, r]

Вот одна из задач Васи, которая уже две недели ему не поддается. Завтра у него День рождения! Давайте сделаем Васе интеллектуальный подарок - напишем быстрый код, который решит его проблему.
Итак, задается N строк, пронумерованных от 1 до N. Ваша программа должна оперативно ответить на Q запросов. Запрос имеет вид: l, r, S. Для каждого запроса программа должна найти, сколько раз строка S встретится на промежутке [l, r].

Формат входных данных:
Первая строка содержит целое число N (1 <= N <= 100000) - количество строк.
Далее идут N строк.
Следующая строка содержит Q (1 <= Q <= 100000) - количество запросов.
Далее идут строки с запросом: l, r, S (1 <= l <= r <= N).
Все строки имеют длину от 5 до 10 символов.

Формат выходных данных:
Для каждого запроса в отдельной строке вывести ответ.

Пример:

Standard input
3
abc
def
abc
3
1 2 abc
1 3 abc
1 2 hgj

Standard output
1
2
0

Если возможно то с коментариями.

0