Макс и Дюк
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
numpalindrome.in
вывод
numpalindrome.out

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

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

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

Входные данные

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

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

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

Выходные данные

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

Пример

Входные данные
8 5
oobokkor
1 3
1 8
2 2
4 7
5 8
Выходные данные
4
12
1
6
5