You are given an array of strings words and a list of range queries queries. Each query is a pair of indices [l_i, r_i] that refers to the subarray words[l_i..r_i] (inclusive).

For each query, return how many strings in the specified range both start and end with a vowel. Vowels are the lowercase letters a, e, i, o, and u.

Return an array of answers in the same order as queries.

Constraints:

• $1 \leq$ words.length $\leq 10^5$

• $1 \leq$ words[i].length $\leq 40$

• words[i] consists only of lowercase English letters

• $\sum$(words[i].length) $\leq 3 \cdot 10^5$

• $1 \leq$ queries.length $\leq 10^5$

• $0 \leq$ l_i $\leq$ r_i $<$ words.length

Input: words = ["oak","tree","idea","unit","sky","echo","rhythm"]-List[str], queries = [[0,6],[1,4],[2,3],[5,5]]-List[List[int]]
Output: [2,1,1,1]-List[int]
Explanation: A word counts if it starts and ends with a vowel (a, e, i, o, u). Checking the words, "oak" (o…k) no, "idea" (i…a) yes, "unit" (u…t) no, and "echo" (e…o) yes. Query [0,6] includes "idea" and "echo" (2), query [1,4] includes "idea" only (1), query [2,3] includes "idea" only (1), and query [5,5] includes "echo" only (1).

Input: words = ["bcd","try","myth","crypt"]-List[str], queries = [[0,3],[1,2],[2,2]]-List[List[int]]
Output: [0,0,0]-List[int]
Explanation: None of the strings start and end with a vowel, so every range query returns 0.

Input: words = ["a","bee","io","up","end","o","use"]-List[str], queries = [[0,0],[0,6],[1,5],[3,4]]-List[List[int]]
Output: [1,4,2,0]-List[int]
Explanation: The valid words are "a" (a…a), "io" (i…o), "o" (o…o), and "use" (u…e), while "end" (e…d), "bee" (b…e), and "up" (u…p) are not. Query [0,0] gives "a" (1), [0,6] gives "a", "io", "o", "use" (4), [1,5] gives "io", "o" (2), and [3,4] covers "up", "end" (0).

Input: words = ["ae","b","civic","umbrella","x","oreo","u"]-List[str], queries = [[0,2],[2,6],[3,3],[4,6]]-List[List[int]]
Output: [1,3,1,2]-List[int]
Explanation: The valid words are "ae" (a…e), "umbrella" (u…a), "oreo" (o…o), and "u" (u…u). Query [0,2] gives "ae" (1), [2,6] gives "umbrella", "oreo", "u" (3), [3,3] gives "umbrella" (1), and [4,6] gives "oreo", "u" (2).

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.