Задача

5 /11


Получите OK


Задача

Дана строка S длины N, состоящая из символов S, T, O и K. Дайте ответ на запросов следующего вида.
Запрос i(1 <= i <= Q): для заданных целых чисел li и r(1 <= li< ri <= N),  рассматривается подстрока S, начинающаяся с индекса li и заканчивающася индексом r(оба включительно). Необходимо определить, сколько раз в этой строке втречается OK как подстрока?
 
Пояснение
Подстрока строки - это строка, полученная удалением нуля или более символов из начала и конца строки исходной строки. Например, для строки KOTS подстроками будут строки KO, KOT, OT, OTS, (пустая строка) и другие, но не OK.


Входные данные
В первой строке записаны два числа N (2<=N<=105) и Q (1<=Q<=105). Во второй строке записана строка S длины N. Каждый символ строки это S, T, O или K. Далее идут Q строк по 2 числа в каждой: li и r(1 <= li< ri <= N).

Выходные данные
Выведите Q строк. I-я строка должна содержать ответ на i-й запрос.
 
Примеры
Входные данные Выходные данные
1 8 3
OKOKTOKS
3 7
2 3
1 8
2
0
3

time 1500 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w6413
Python64
Комментарий учителя