this is a previous interview that happned with my frined an he said after solving the problem ther will be a round 2 and 
Part 2: A follow up discussion over the solution for Part 1 and 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.
"""
# 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()

"""
please explain and give a solution worthy