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

Input 1

10 3
abbabbbaab
1 2
1 5
0 7

Output 1

0
2
8

Input 2

10 3
bbababbaba
0 4
5 9
0 9

Output 2

1
1
8

Input 2

10 1
aaaaabbbbb
0 9

Output 2

25