for the ps :
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

"""
which code is better 
"""
import sys

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

class Tree:
    def __init__(self, m, n, name_list):
        self.node_list = []
        self.node_map = {}
        self.locked_nodes = set()  
        self.time = 0
        self.in_time = {}
        self.out_time = {}

        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_index = m * i + j + 1
                if child_index < n:
                    self.node_list[i].child.append(self.node_list[child_index])
                    self.node_list[child_index].parent = self.node_list[i]

        self.root = self.node_list[0]

        self.dfs(self.root)

    def dfs(self, node):
        self.time += 1
        self.in_time[node] = self.time
        for child in node.child:
            self.dfs(child)
        self.time += 1
        self.out_time[node] = self.time

    def is_descendant(self, ancestor, node):
        """Check if `node` is a descendant of `ancestor` using in-time and out-time."""
        return self.in_time[ancestor] < self.in_time[node] and self.out_time[node] < self.out_time[ancestor]

    def lock(self, node, uid):
        if node.isLocked:
            return False

        if self.isAncestorLocked(node):
            return False

        if node.lockedDescendantCount > 0:
            return False

        # Lock the node
        node.isLocked = True
        node.uid = uid
        self.locked_nodes.add(node)  # Add node to locked nodes set

        # Update the lockedDescendantCount for ancestors
        parent = node.parent
        while parent:
            parent.lockedDescendantCount += 1
            parent = parent.parent

        return True

    def unlock(self, node, uid):
        if not node.isLocked or node.uid != uid:
            return False

        # Unlock the node
        node.isLocked = False
        node.uid = None
        self.locked_nodes.remove(node)  # Remove node from locked nodes set

        # Update the lockedDescendantCount for ancestors
        parent = node.parent
        while parent:
            parent.lockedDescendantCount -= 1
            parent = parent.parent

        return True

    def upgrade(self, node, uid):
        if node.isLocked:
            return False

        if self.isAncestorLocked(node):
            return False

        if node.lockedDescendantCount == 0:
            return False

        # Collect all locked descendants using precomputed locked nodes
        locked_descendants = []
        for locked_node in self.locked_nodes:
            if self.is_descendant(node, locked_node) and locked_node.uid == uid:
                locked_descendants.append(locked_node)
            elif self.is_descendant(node, locked_node) and locked_node.uid != uid:
                return False  # Locked by a different user

        # Unlock all locked descendants
        for descendant in locked_descendants:
            descendant.isLocked = False
            descendant.uid = None
            self.locked_nodes.remove(descendant)  # Remove from locked nodes set

            # Update the lockedDescendantCount for ancestors
            parent = descendant.parent
            while parent:
                parent.lockedDescendantCount -= 1
                parent = parent.parent

        # Lock the current node
        node.isLocked = True
        node.uid = uid
        self.locked_nodes.add(node)  # Add node to locked nodes set

        # Update the lockedDescendantCount for ancestors
        parent = node.parent
        while parent:
            parent.lockedDescendantCount += 1
            parent = parent.parent

        return True

    def isAncestorLocked(self, node):
        """Check if any of the ancestors of the given node are locked."""
        curr = node.parent
        while curr:
            if curr.isLocked:
                return True
            curr = curr.parent
        return False

    def process_queries(self, queries):
        results = []
        for query in queries:
            operation, node_name, uid = query.strip().split()
            uid = int(uid)
            node = self.node_map[node_name]
            if operation == "1":
                result = self.lock(node, uid)
            elif operation == "2":
                result = self.unlock(node, uid)
            elif operation == "3":
                result = self.upgrade(node, uid)
            else:
                result = False  # Invalid operation
            results.append('true' if result else 'false')
        return results

def main():
    n = int(sys.stdin.readline())
    m = int(sys.stdin.readline())
    q = int(sys.stdin.readline())
    name_list = []
    queries = []

    for _ in range(n):
        name_list.append(sys.stdin.readline().strip())

    for _ in range(q):
        queries.append(sys.stdin.readline().strip())

    tree = Tree(m, n, name_list)
    results = tree.process_queries(queries)
    for res in results:
        print(res)

main()

"""
"""
import sys

class Node:
    def __init__(self, name):
        self.name = name
        self.parent = None
        self.children = []
        self.isLocked = False
        self.locked_uid = None
        self.locked_descendant_count = 0  # Number of locked descendants

class Tree:
    def __init__(self, m, n, 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

        # Build the tree
        for i in range(n):
            for j in range(m):
                child_index = m * i + j + 1
                if child_index < n:
                    self.node_list[i].children.append(self.node_list[child_index])
                    self.node_list[child_index].parent = self.node_list[i]

        self.root = self.node_list[0]
        
    def lock(self, node, uid):
        if node.isLocked:
            return False
        
        # Check if any ancestor is locked
        current = node.parent
        while current:
            if current.isLocked:
                return False
            current = current.parent
        
        if node.locked_descendant_count > 0:
            return False
        
        # Lock the node
        node.isLocked = True
        node.locked_uid = uid
        
        # Update locked_descendant_count for all ancestors
        current = node.parent
        while current:
            current.locked_descendant_count += 1
            current = current.parent
        
        return True
    
    def unlock(self, node, uid):
        if not node.isLocked or node.locked_uid != uid:
            return False
        
        # Unlock the node
        node.isLocked = False
        node.locked_uid = None
        
        # Update locked_descendant_count for all ancestors
        current = node.parent
        while current:
            current.locked_descendant_count -= 1
            current = current.parent
        
        return True
    
    def upgrade(self, node, uid):
        if node.isLocked:
            return False
        
        # Check if any ancestor is locked
        current = node.parent
        while current:
            if current.isLocked:
                return False
            current = current.parent
        
        if node.locked_descendant_count == 0:
            return False
        
        # Collect all locked descendants
        locked_nodes = []
        self._collect_locked_descendants(node, locked_nodes)
        
        if not locked_nodes:
            return False
        
        # Ensure all locked descendants have the same uid
        for locked_node in locked_nodes:
            if locked_node.locked_uid != uid:
                return False
        
        # Unlock all locked descendants
        for locked_node in locked_nodes:
            locked_node.isLocked = False
            locked_node.locked_uid = None
            # Update locked_descendant_count for ancestors of each unlocked node
            ancestor = locked_node.parent
            while ancestor:
                ancestor.locked_descendant_count -= 1
                ancestor = ancestor.parent
        
        # Lock the current node
        node.isLocked = True
        node.locked_uid = uid
        
        # Update locked_descendant_count for all ancestors
        current = node.parent
        while current:
            current.locked_descendant_count += 1
            current = current.parent
        
        return True
    
    def _collect_locked_descendants(self, node, locked_nodes):
    # DFS to collect all locked descendants
        stack = []
        stack.append(node)
        while stack:
            current = stack.pop()
            for child in current.children:
                if child.locked_descendant_count == 0 and not child.isLocked:
                    continue  # No need to traverse this subtree
                if child.isLocked:
                    locked_nodes.append(child)
                stack.append(child)    
                
    def process_queries(self, queries):
        results = []
        for query in queries:
            parts = query.strip().split()
            if len(parts) != 3:
                results.append('false')
                continue
            operation, node_name, uid_str = parts
            try:
                uid = int(uid_str)
            except ValueError:
                results.append('false')
                continue
            node = self.node_map.get(node_name, None)
            if not node:
                results.append('false')
                continue
            if operation == "1":
                result = self.lock(node, uid)
            elif operation == "2":
                result = self.unlock(node, uid)
            elif operation == "3":
                result = self.upgrade(node, uid)
            else:
                result = False  # Invalid operation
            results.append('true' if result else 'false')
        return results

def main():

    input = sys.stdin.read
    data = input().splitlines()
    ptr = 0
    if ptr >= len(data):
        sys.exit()
    n = int(data[ptr]); ptr +=1
    if ptr >= len(data):
        sys.exit()
    m = int(data[ptr]); ptr +=1
    if ptr >= len(data):
        sys.exit()
    q = int(data[ptr]); ptr +=1
    name_list = []
    for _ in range(n):
        if ptr >= len(data):
            break
        name_list.append(data[ptr].strip())
        ptr +=1
    queries = []
    for _ in range(q):
        if ptr >= len(data):
            break
        queries.append(data[ptr].strip())
        ptr +=1
    tree = Tree(m, n, name_list)
    results = tree.process_queries(queries)
    for res in results:
        print(res)

if __name__ == "__main__":
    main()
"""