Question
Vowel Count in Range Queries
You are given a string KaTeX can only parse string typed expression of length KaTeX can only parse string typed expression consisting of lowercase English letters. You are also given KaTeX can only parse string typed expression queries.
In each query, two indices KaTeX can only parse string typed expression and KaTeX can only parse string typed expression (0-indexed) are given. Your task is to determine the number of vowels present in the substring from index KaTeX can only parse string typed expression to KaTeX can only parse string typed expression (inclusive).
The vowels are KaTeX can only parse string typed expression.
Input
The first line contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression — the length of the string and the number of queries.
The second line contains a string KaTeX can only parse string typed expression of length KaTeX can only parse string typed expression.
Each of the next KaTeX can only parse string typed expression lines contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression — representing the query range.
The second line contains a string KaTeX can only parse string typed expression of length KaTeX can only parse string typed expression.
Each of the next KaTeX can only parse string typed expression lines contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression — representing the query range.
Output
For each query, print a single integer — the number of vowels in the substring KaTeX can only parse string typed expression.
Example
Input
9 3
abecidofu
0 4
2 6
3 7
Output
3
3
2
Explanation
Query (0, 4) → substring = "abeci" → vowels = a, e, i → total = 3
Query (2, 6) → substring = "ecido" → vowels = e, i, o → total = 3
Query (3, 8) → substring = "cidof" → vowels = i, o → total = 2
9 3
abecidofu
0 4
2 6
3 7
Output
3
3
2
Explanation
Query (0, 4) → substring = "abeci" → vowels = a, e, i → total = 3
Query (2, 6) → substring = "ecido" → vowels = e, i, o → total = 3
Query (3, 8) → substring = "cidof" → vowels = i, o → total = 2