Ось одна із задач Василька, яка уже два тижні йому не піддається. Завтра у нього День народження! Давайте зробимо Васильку інтелектуальний подарунок - напишемо швидкий код, який вирішить його проблему.
Отже, задається N рядків, пронумерованих від 1 до \(N\).
Ваша програма повинна оперативо відповісти на \(Q\) запитів. Запит має вигляд: \(l, r, S\).
Для кожного запиту програма повинна знайти, скільки разів рядок \(S\) зустрінеться на проміжку \([l, r]\).
Формат вхідних даних
Перший рядок містить ціле число \(N\) \((1 \le N \le 100000)\) - кількість рядків.
Далі ідуть \(N\) рядків.
Наступний рядок містить \(Q\) \((1 \le Q \le 100000)\) - кількість запитів.
Далі ідуть рядки із запитом: \(l, r, S\) \((1 \le l \le r \le N)\).
Всі рядки мають довжину від 5 до 10 символів.
Формат вихідних даних
Для кожного запиту в окремому рядки вивести відповідь
Приклад вхідних даних
3
abc
def
abc
3
1 2 abc
1 3 abc
1 2 hgj
Приклад вихідних даних
1
2
0
Коментарі
Додайте часу на Python, будь ласка (або скажіть, що можна написати ефективніше рішення цією мовою) Просто аналогічне рішення на С++ набирає 100/100
Добавив...