AB Subs

Problem Statement

You are give an initial string $s$ of length $n$ consisting of only the letters a and b.

You are also given $q$ queries, in order, each containing two integers $l$ and $r$.

For each query, determine the number of ab subsequences in the substring of $s$ from $l$ to $r$.

Input Format

Your first line will contain $n$ and $q$. Your next line will contain $s$. Your next $q$ lines will contain two integers each, representing $l$ and $r$ for that query.

Output Format

For each each query, you should output one line containing a single integer representing the number of ab subsequences from that query's substring.

Constraints

Subtask 1

• $1 \leq n, q \leq 10^3$
• $0 \leq l \leq r \leq n - 1$

Subtask 2

• $1 \leq n, q \leq 10^5$
• $0 \leq l \leq r \leq n - 1$

Sample Cases

10 3
abbabbbaab
1 2
1 5
0 7

0
2
8

10 3
bbababbaba
0 4
5 9
0 9

1
1
8

10 1
aaaaabbbbb
0 9

25