class TrieNode:
    def __init__(self):
        self.children = {}
        self.min_len = float("inf")
        self.idx = float("inf")

class Trie:
    def __init__(self):
        self.root = TrieNode()
        
    def insert(self, s: str, idx: int):
        node = self.root
        if len(s) < node.min_len:
            node.min_len = len(s)
            node.idx = idx
            
        for ch in s:
            c = ch
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
            
            if len(s) < node.min_len:
                node.min_len = len(s)
                node.idx = idx