맥스와 듀크

맥스와 듀크는 육가공 공장에 들어갔다가 아주 긴 소시지 사슬을 발견했다. 이 사슬은 문자열 $s$로 나타낼 수 있으며, 소시지 하나는 소문자 라틴 알파벳 한 글자에 대응한다.

소시지 구간 $[a, b]$의 연속된 나열을 뒤집었을 때 원래와 같으면 이 구간을 맛있다고 부른다. 맥스는 매 순간 구간 $[l, r]$을 보고 듀크에게 이상한 질의를 한다. 맥스가 보는 맛있는 부분 구간이 몇 개인지 묻는 질의다.

$l \le a \le b \le r$을 만족하고 구간 $[a, b]$가 맛있는 $a$와 $b$의 쌍의 개수를 구하라.

첫 줄에 정수 $n$과 $m$이 주어진다. $n$은 문자열 $s$의 길이이고, $m$은 질의의 개수이다 ($1 \le n,m \le 500\,000$).

둘째 줄에는 길이가 $n$인 소문자 라틴 알파벳 문자열 $s$가 주어진다.

이어서 $m$개의 줄에 $i$번째 질의의 경계 $l$과 $r$이 주어진다 ($1 \le l \le r \le n$).

각 질의에 대해 맛있는 부분 구간의 개수를 출력한다.