make only the locking mechanism in the code thread-safe, ignoring the unlock and upgrade lock mechanisms for the time being.
I mentioned using mutex/semaphore locks, but that wasn’t acceptable.
some new constraints regarding thread safety with and without the use of mutex. This round was based on slack and google meet and lasted for about 7 hours (give or take 😐). TIP: try to assume that the kernel doesn't support mutex and try to design one of your own.

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.

explore all solutions like in interview scenrio i dont know what they will ask give me porper and explain so that i can ace the interview 
"""
# 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          # Node value (name)
        self.uid = None         # User ID who locked the node
        self.parent = None      # Reference to parent node
        self.children = []      # List of child nodes
        self.isLocked = False   # Lock status
        self.lockedDescendantCount = 0  # Number of locked descendants


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

        # Create node instances and map node names to instances
        for name in node_list:
            node = Node(name)
            self.node_list.append(node)
            self.node_map[name] = node

        # Assign children to each node based on m-ary tree properties
        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]

        # Process queries
        self.processed_queries = [query.strip().split() for query in queries]

    def lock(self, node, uid):
        # Check if node is already locked
        if node.isLocked:
            return False

        # Check if any ancestors are locked
        if self.isAncestorLocked(node):
            return False

        # Check if any descendants are locked
        if node.lockedDescendantCount > 0:
            return False

        # Lock the node
        node.isLocked = True
        node.uid = uid

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

        return True

    def unlock(self, node, uid):
        # Check if node is locked by uid
        if not node.isLocked or node.uid != uid:
            return False

        # Unlock the node
        node.isLocked = False
        node.uid = None

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

        return True

    def upgrade(self, node, uid):
        # Check if node is already locked
        if node.isLocked:
            return False

        # Check if any ancestors are locked
        if self.isAncestorLocked(node):
            return False

        # Check if there are any locked descendants
        if node.lockedDescendantCount == 0:
            return False  # No locked descendants to upgrade

        # Collect all locked descendants
        locked_descendants = []
        if not self.collectLockedDescendants(node, uid, locked_descendants):
            return False  # Cannot upgrade due to locks by other users

        # Unlock all locked descendants
        for descendant in locked_descendants:
            descendant.isLocked = False
            descendant.uid = None
            # Update ancestors' lockedDescendantCount
            parent = descendant.parent
            while parent:
                parent.lockedDescendantCount -= 1
                parent = parent.parent

        # Lock the node
        node.isLocked = True
        node.uid = uid

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

        return True

    def isAncestorLocked(self, node):
        # Traverse up to check if any ancestor is locked
        current = node.parent
        while current:
            if current.isLocked:
                return True
            current = current.parent
        return False

    def collectLockedDescendants(self, node, uid, locked_nodes):
        # If there are no locked descendants, return True
        if node.lockedDescendantCount == 0:
            return True

        # Check if current node is locked
        if node.isLocked:
            if node.uid == uid:
                locked_nodes.append(node)
            else:
                # Locked by a different user
                return False

        # Recurse into children only if necessary
        for child in node.children:
            if child.lockedDescendantCount > 0:
                if not self.collectLockedDescendants(child, uid, locked_nodes):
                    return False
        return True

    def process_queries(self):
        results = []
        for query in self.processed_queries:
            operation, node_name, uid = query
            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())

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

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

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

main()

"""