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