Implement a Trie for UPI ID Autocomplete

Problem

Implement a Trie (prefix tree) that supports UPI ID autocomplete.

Required operations

• insert(upiId) — add a UPI ID (e.g., "shivam@paytm")
• search(upiId) → true/false exact match
• startsWith(prefix) → true/false prefix exists
• autocomplete(prefix, topK) → return up to K UPI IDs matching the prefix, sorted by frequency

Example

insert("alice@paytm") x3, insert("alex@paytm") x1, insert("bob@upi") x2
autocomplete("al", 2) -> ["alice@paytm", "alex@paytm"]