Модуль: Два указателя

Дана строка 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⁵) и Q (1<=Q<=10⁵). Во второй строке записана строка 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

Напишите программу