Let’s say you are running the lock/unlock in a multi core machine. Now you want to let multiple threads to run lock() As we saw in part A, locking a node has multiple validations inside. Will doing lock on two nodes cause a race condition. If yes, how will you solve it. In short,
how do make the lock() function thread safe? - Multiple threads running it simultaneously shouldn’t not affect the correctness. -Try to make the critical sections more granular.
ie. don’t create any big atomic/synchronised blocks that will make parallelism suffer.
Consider each operation is atomic.
Implement thread safe concurrent lock method without using any atomic method, mutex, semaphores, synchronized keywork
dont use any inbuilt threading show logicwrute the code ahand wruteetn in as in interview  
"""

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()

"""
explain show me so that i can learn and so it