can you think of any other testcase or edge case that this approach will not solve or fail like go into depth as deep and ensure it is the best for this ignore about threads part 
"""
Question 1: Locking the Tree of Space
You have a world map represented as an M-Ary tree (sample tree below):

You need to define three operations on it:
lock(X, uid)
unlock(X, uid)
upgradeLock(X, uid)
Where X is the name of a node in the tree (which is unique), and uid is the user performing the operation.
Definitions for the Operations:
Lock(X, uid):
Lock takes exclusive access on the subtree rooted at X. Once lock(X, uid) succeeds:
lock(A, anyUserId) should fail (returns false), where A is a descendant of X.
lock(B, anyUserId) should fail (returns false), where X is a descendant of B.
Lock operation cannot be performed on a node that is already locked, i.e., lock(X, anyUserId) should fail (returns false).
Unlock(X, uid):
Unlock reverts what was done by the lock operation. It can only be called on the same node on which user uid had called a lock before. Returns true if successful.
UpgradeLock(X, uid):
This helps the user uid upgrade their lock to an ancestor node. It is only possible if the node X already has locked descendants and all of them are locked by the same user uid. Upgrade should fail if there is any node which is a descendant of X that is locked by a different user. A successful upgrade will "lock" the node. UpgradeLock must not violate the consistency model required by Lock/Unlock.
Notes:
The number of nodes in the tree, N, is very large, so optimize the time complexity for the above algorithms.
Input Format:


The first line contains the number of nodes in the tree (N).
The second line contains the number of children per node (m in an m-ary tree).
The third line contains the number of queries (Q).
Next N lines contain the NodeName (string) in the m-Ary Tree.
The next Q lines contain queries in the format: OperationType NodeName UserId.
Operation Type:
1 for Lock
2 for Unlock
3 for UpgradeLock
NodeName: The name of any node (unique) in the m-Ary Tree.
UserId: An integer representing a unique user.
Example Input:
7
2
3
World
Asia
Africa
China
India
South Africa
Egypt
1 China 9
2 India 9
3 Asia 9


This input represents a 2-ary tree with 7 nodes as follows:
           World
           /     \
      Asia        Africa
     /    \       /     \
 China  India  South Africa  Egypt


Additional Notes:
The tree is always fully balanced.
Constraints:
(1 < N < 5 \times 10^5)
(1 < m < 30)
(1 < Q < 5 \times 10^5)
(1 < \text{length of NodeName} < 20)
Optimize the time complexity:
Lock: (O(\log_m N))
Unlock: (O(\log_m N))
UpgradeLock: (O(\text{numberOfLockedNodes} \times \log_m N))
The lock operation on an already locked node should fail.
Once UpgradeLock(X, uid) succeeds on X, it is equivalent to X being locked by uid. As per the definition, Lock(A/B, anyUser) should fail, and Unlock(X, uid) should also work.
Upgrade lock operation on a node having no locked descendants should fail, and upgrade lock on an already locked node should also fail.

"""
"""
import sys

class Node:
    def __init__(self, val):
        self.val = val
        self.uid = None
        self.parent = None
        self.child = []
        self.desc_set = set()
        self.isLocked = False

class M_Arr_Tree:
    def __init__(self, n, m, name_list):
        self.node_list = []
        self.node_map = {}

        for name in name_list:
            node = Node(name)
            self.node_list.append(node)
            self.node_map[name] = node
        
        for i in range(n):
            for j in range(m):
                child_idx = m * i + j + 1
                if child_idx < n:
                    self.node_list[i].child.append(self.node_list[child_idx])
                    self.node_list[child_idx].parent = self.node_list[i]
        
        self.root = self.node_list[0]

    def Lock(self, node, uid):
        if node.isLocked:
            return 'false'
        
        curr = node.parent
        while curr:
            if curr.isLocked:
                return 'false'
            curr = curr.parent

        if node.desc_set:
            return 'false'
        
        node.isLocked = True
        node.uid = uid

        curr = node.parent
        while curr:
            curr.desc_set.add(node)
            curr = curr.parent
        
        return 'true'

    def Unlock(self, node, uid):
        if not node.isLocked or node.uid != uid:
            return 'false'
        
        node.isLocked = False
        node.uid = None

        curr = node.parent
        while curr:
            curr.desc_set.discard(node)
            curr = curr.parent
        
        return 'true'

    def Upgrade(self, node, uid):
        if node.isLocked:
            return 'false'
        
        curr = node.parent
        while curr:
            if curr.isLocked:
                return 'false'
            curr = curr.parent
        
        locked_descs = list(node.desc_set)

        if not locked_descs:
            return 'false'
        
        for ld in locked_descs:
            if ld.uid != uid:
                return 'false'
        
        for ld in locked_descs:
            ld.isLocked = False
            ld.uid = None
            node.desc_set.discard(ld)

            curr = ld.parent
            while curr:
                curr.desc_set.discard(ld)
                curr = curr.parent
        
        node.isLocked = True
        node.uid = uid

        curr = node.parent
        while curr:
            curr.desc_set.add(node)
            curr = curr.parent
        
        return 'true'
    
    def Process(self, queries):
        res = []
        for q in queries:
            parts = q.strip().split()
            if len(parts) != 3:
                res.append('false')
                continue
            ops, node_name, uid = parts
            uid = int(uid)
            node = self.node_map.get(node_name, None)
            if ops == '1':
                res.append(self.Lock(node, uid))
            elif ops == '2':
                res.append(self.Unlock(node, uid))
            elif ops == '3':
                res.append(self.Upgrade(node, uid))
            else:
                res.append('false') 
        return res

def main():
    n = int(sys.stdin.readline().strip())
    m = int(sys.stdin.readline().strip())
    q = int(sys.stdin.readline().strip())

    name_list = []
    for _ in range(n):
        name = sys.stdin.readline().strip()
        name_list.append(name)

    queries = []
    for _ in range(q):
        query = sys.stdin.readline().strip()
        queries.append(query)
    
    tree = M_Arr_Tree(n, m, name_list)
    res = tree.Process(queries)
    for r in res:
        print(r)
main()

"""