Count Words Sharing a Prefix

You are given a list of words words (duplicates allowed) and a list of query strings prefixes. For every query return how many words in words start with that prefix. Duplicated words count every time they appear. The empty prefix "" matches every word.

Return the counts as a list in the same order as prefixes.

Examples

Input:  words = ["apple", "app", "apricot", "banana"], prefixes = ["ap", "app", "b", "c"]
Output: [3, 2, 1, 0]
Explanation: "ap" starts apple, app and apricot; "app" starts apple and app; nothing starts with "c".

Input:  words = ["go", "go", "gone"], prefixes = ["go", ""]
Output: [3, 3]

Constraints

• 0 <= len(words), len(prefixes) <= 2 * 10**4
• Words and prefixes consist of lowercase letters and digits; total characters <= 2 * 10**5
• Target: O(total characters) to build plus O(len(prefix)) per query. Scanning all words for every query is too slow.

Goals

• Build a trie whose nodes remember how many words pass through them
• Answer many prefix queries without rescanning the word list each time