Prefix Word Search Data Structure (Trie Autocomplete)

Problem: Prefix Query (Trie Autocomplete) Given a list of words words (lowercase letters a-z only), build a data structure that supports: build(words): insert all words into the structure. query(prefix): given a prefix prefix, return all words that start with this prefix. Output Requirements query(prefix) returns a list of strings containing all matching words. No specific order is required (unless you choose to sort). Constraints 1 <= len(words) <= 2 * 10^5 1 <= len(word) <= 30 1 <= Q <= 2 * 10^5 0 <= len(prefix) <= 30 All characters are in a-z. Must be efficient for many queries (cannot scan all words per query). Notes A Trie (prefix tree) is recommended: Insert: create nodes along characters. Query: traverse to the node for prefix, then DFS/backtrack to collect complete words. Sample I/O (stdin / stdout) Suggested input format: Line 1: integer n Next n lines: one word per line Next line: integer q Next q lines: one prefix per line Output: For each prefix, print one line: all matched words separated by spaces; print an empty line if none. Example Input 5 apple app ape bat bath 3 ap app ba Output apple app ape apple app bat bath