Deterministic Solution using Trie and indices in TrieNode
\nimport bisect\n\nclass TrieNode:\n    def __init__(self):\n        self.child = {}\n        self.pos = []\n\nclass Trie:\n    def __init__(self):\n        sel
```\nimport bisect\n\nclass TrieNode:\n    def __init__(self):\n        self.child = {}\n        self.pos = []\n\nclass Trie:\n    def __init__(self):\n        self.root = TrieNode()\n\n    def insert(self, s, i):\n        curr = self.root\n        curr.pos.append(i)\n        for c in s:\n            if c not in curr.child:\n                curr.child[c] = TrieNode()\n            curr = curr.child[c]\n            curr.pos.append(i)\n\n    def check(self, s):\n        curr = self.root\n        for c in s:\n            if c not in curr.child or curr.child[c].ctr == 0:\n                return False\n            curr = curr.child[c]\n        return curr.end\n    \n    def majority(self, l, r, threshold):\n        curr = self.root\n        res = 0\n        freq = 0\n        while True:\n            maxchild = (-1, None)\n            for c in curr.child:\n                ctr = bisect.bisect_right(curr.child[c].pos, r) - bisect.bisect_left(curr.child[c].pos, l)\n                maxchild = max(maxchild, (ctr, c))\n            if maxchild[1] != None:\n                freq = maxchild[0]\n                curr = curr.child[maxchild[1]]\n                res = 10 * res + int(maxchild[1])\n            else:\n                break\n        if freq < threshold:\n            return -1\n        return res\n\nclass MajorityChecker:\n    def __init__(self, arr: List[int]):\n        n = len(arr)\n        self.trie = Trie()\n        pad = lambda x: "{:06d}".format(x)\n        for i in range(n):\n            self.trie.insert(pad(arr[i]), i)\n\n    def query(self, left: int, right: int, threshold: int) -> int:\n        return self.trie.majority(left, right, threshold)\n```
[]