Задача
Дана строка
S длины
N, состоящая из символов
S,
T,
O и
K. Дайте ответ на
Q запросов следующего вида.
Запрос
i(1 <= i <= Q): для заданных целых чисел
li и
ri (1 <= l
i< r
i <= N), рассматривается подстрока
S, начинающаяся с индекса
li и заканчивающася индексом
ri (оба включительно). Необходимо определить, сколько раз в этой строке втречается
OK как подстрока?
Пояснение
Подстрока строки - это строка, полученная удалением нуля или более символов из начала и конца строки исходной строки. Например, для строки
KOTS подстроками будут строки
KO,
KOT,
OT,
OTS, (пустая строка) и другие, но не
OK.
Входные данные
В первой строке записаны два числа
N (2<=N<=10
5) и
Q (1<=Q<=10
5). Во второй строке записана строка
S длины
N. Каждый символ строки это
S,
T,
O или
K. Далее идут
Q строк по 2 числа в каждой:
li и
ri (1 <= l
i< r
i <= N).
Выходные данные
Выведите
Q строк.
I-я строка должна содержать ответ на
i-й запрос.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
8 3
OKOKTOKS
3 7
2 3
1 8 |
2
0
3 |