Vowels in Substrings

Given a lowercase string s and a list of queries [l, r], return, for each query, how many vowels (a e i o u) appear in s[l..r] inclusive.

Examples

Input:  s = "abcdeiou", queries = [[0, 2], [3, 7], [4, 4]]
Output: [1, 4, 1]

Input:  s = "xyz", queries = [[0, 2]]
Output: [0]

Constraints

• 1 <= len(s) <= 10**5, 0 <= len(queries) <= 10**5
• 0 <= l <= r < len(s)
• Target complexity: O(n + q). Counting inside each substring separately is too slow.

Goals

• Build a prefix count over a predicate
• Answer many substring queries in O(1) each