시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 1024 MB73342.857%

문제

Макс и Дюк попали на мясокомбинат и нашли длинную-предлинную цепочку сосисок, которую можно представить как строку $s$, каждой сосиске соответствует маленькая латинская буква.

Они считают отрезок сосисок $[a, b]$ вкусным, если непрерывная последовательность сосисок с $a$ по $b$ совпадает с этой же последовательностью в перевернутом виде. В каждый момент Макс наблюдает за отрезком сосисок $[l, r]$ и задает Дюку странные запросы: сколько вкусных подотрезков видит Макс.

Вам необходимо узнать количество пар $a$ и $b$ таких, что $l \le a \le b \le r$ и отрезок $[a, b]$ вкусный.

입력

В первой строке задано число $n$ и $m$ --- длина строки $s$ и количество запросов ($1 \le n,m \le 500\,000$).

Во второй строке задана последовательность маленьких латинских букв длины $n$ --- строка $s$.

Далее следует $m$ строк. В каждой записаны числа $l$ и $r$ --- границы i-го запроса ($1 \le l \le r \le n$).

출력

Для каждого запроса выведите количество вкусных подотрезков.

예제 입력 1

8 5
oobokkor
1 3
1 8
2 2
4 7
5 8

예제 출력 1

4
12
1
6
5