Макс и Дюк

Макс и Дюк попали на мясокомбинат и нашли длинную-предлинную цепочку сосисок, которую можно представить как строку $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$).

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