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


ignore about Gil and stuff in interview imporatnt ot demonstrate coding and logic right so make it good