hey there i am preapring for interviewr and i have made a list like what might happend in interview 
now how i understood the problem
how i got the intituation for thr solution
understan hte time complexity and space compelxity of the present soltion
how i can optimze it 
optimze the code and write up teh code 
maybe have a talk conditions, the multi-threading environment and critical section
think about ho to make ut threadsafe

thin kabout how to think about making the problem threadsafe 


and this is the code 
"""
import sys

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

class M_Arr_Tree:
    def __init__(self, n, m, 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
        
        for i in range(n):
            for j in range(m):
                child_idx = m * i + j + 1
                if child_idx < n:
                    self.node_list[i].child.append(self.node_list[child_idx])
                    self.node_list[child_idx].parent = self.node_list[i]
        
        self.root = self.node_list[0]

    def Lock(self, node, uid):
        if node.isLocked:
            return 'false'
        
        curr = node.parent
        while curr:
            if curr.isLocked:
                return 'false'
            curr = curr.parent

        if node.desc_set:
            return 'false'
        
        node.isLocked = True
        node.uid = uid

        curr = node.parent
        while curr:
            curr.desc_set.add(node)
            curr = curr.parent
        
        return 'true'

    def Unlock(self, node, uid):
        if not node.isLocked or node.uid != uid:
            return 'false'
        
        node.isLocked = False
        node.uid = None

        curr = node.parent
        while curr:
            curr.desc_set.discard(node)
            curr = curr.parent
        
        return 'true'

    def Upgrade(self, node, uid):
        if node.isLocked:
            return 'false'
        
        curr = node.parent
        while curr:
            if curr.isLocked:
                return 'false'
            curr = curr.parent
        
        locked_descs = list(node.desc_set)

        if not locked_descs:
            return 'false'
        
        for ld in locked_descs:
            if ld.uid != uid:
                return 'false'
        
        for ld in locked_descs:
            ld.isLocked = False
            ld.uid = None
            node.desc_set.discard(ld)

            curr = ld.parent
            while curr:
                curr.desc_set.discard(ld)
                curr = curr.parent
        
        node.isLocked = True
        node.uid = uid

        curr = node.parent
        while curr:
            curr.desc_set.add(node)
            curr = curr.parent
        
        return 'true'
    
    def Process(self, queries):
        res = []
        for q in queries:
            parts = q.strip().split()
            if len(parts) != 3:
                res.append('false')
                continue
            ops, node_name, uid = parts
            uid = int(uid)
            node = self.node_map.get(node_name, None)
            if ops == '1':
                res.append(self.Lock(node, uid))
            elif ops == '2':
                res.append(self.Unlock(node, uid))
            elif ops == '3':
                res.append(self.Upgrade(node, uid))
            else:
                res.append('false') 
        return res

def main():
    n = int(sys.stdin.readline().strip())
    m = int(sys.stdin.readline().strip())
    q = int(sys.stdin.readline().strip())

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

    queries = []
    for _ in range(q):
        query = sys.stdin.readline().strip()
        queries.append(query)
    
    tree = M_Arr_Tree(n, m, name_list)
    res = tree.Process(queries)
    for r in res:
        print(r)
main()

"""

i want to genereate liek all possible questions will be asked in interview like all if there10000 give me 10000 questions and give me everything 
"""
and this is my threadsafe code like i am thinking of giving it to him in two step like first i will give him a spinlock one and then i will give abetter optimzed readwrite one like this 
"""
import sys

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

class M_Arr_Tree:
    def __init__(self, n, m, 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
        
        for i in range(n):
            for j in range(m):
                child_idx = m * i + j + 1
                if child_idx < n:
                    self.node_list[i].children.append(self.node_list[child_idx])
                    self.node_list[child_idx].parent = self.node_list[i]
        
        self.root = self.node_list[0]

    def _update_lock_count_upwards(self, node, delta):
        current = node.parent
        while current:
            current.locked_descendant_count += delta
            current = current.parent

    def Lock(self, node, uid):
        if node.isLocked or node.locked_descendant_count > 0:
            return 'false'

        # Check if any ancestors are locked
        current = node.parent
        while current:
            if current.isLocked:
                return 'false'
            current = current.parent

        node.isLocked = True
        node.uid = uid
        self._update_lock_count_upwards(node, 1)
        return 'true'

    def Unlock(self, node, uid):
        if not node.isLocked or node.uid != uid:
            return 'false'
        
        node.isLocked = False
        node.uid = None
        self._update_lock_count_upwards(node, -1)
        return 'true'

    def Upgrade(self, node, uid):
        if node.isLocked or node.locked_descendant_count == 0:
            return 'false'

        # Check if any ancestors are locked
        current = node.parent
        while current:
            if current.isLocked:
                return 'false'
            current = current.parent

        # Collect all locked descendants
        locked_nodes = []
        stack = [node]
        while stack:
            current = stack.pop()
            if current.isLocked:
                locked_nodes.append(current)
            for child in current.children:
                stack.append(child)

        if not locked_nodes:
            return 'false'

        # Ensure all locked descendants are locked by the same uid
        for ld in locked_nodes:
            if ld.uid != uid:
                return 'false'

        # Unlock all descendants
        for ld in locked_nodes:
            ld.isLocked = False
            ld.uid = None
            self._update_lock_count_upwards(ld, -1)

        # Lock the current node
        node.isLocked = True
        node.uid = uid
        self._update_lock_count_upwards(node, 1)

        return 'true'
    
    def Process(self, queries):
        res = []
        for q in queries:
            parts = q.strip().split()
            if len(parts) != 3:
                res.append('false')
                continue
            ops, node_name, uid = parts
            uid = int(uid)
            node = self.node_map.get(node_name, None)
            if not node:
                res.append('false')
                continue
            if ops == '1':
                res.append(self.Lock(node, uid))
            elif ops == '2':
                res.append(self.Unlock(node, uid))
            elif ops == '3':
                res.append(self.Upgrade(node, uid))
            else:
                res.append('false') 
        return res

def main():
    n = int(sys.stdin.readline().strip())
    m = int(sys.stdin.readline().strip())
    q = int(sys.stdin.readline().strip())

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

    queries = []
    for _ in range(q):
        query = sys.stdin.readline().strip()
        queries.append(query)
    
    tree = M_Arr_Tree(n, m, name_list)
    res = tree.Process(queries)
    for r in res:
        print(r)
        
if __name__ == "__main__":
    main()



"""
import sys
import threading

class Node:
    def __init__(self, val):
        self.val = val
        self.uid = None
        self.parent = None
        self.children = []
        self.locked_descendant_count = 0
        self.isLocked = False
        self.state_lock = False  # Custom lock flag

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

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

        self.root = self.node_list[0]

    def _acquire_node_lock(self, node):
        # Custom non-blocking lock acquisition
        while True:
            if not node.state_lock:
                node.state_lock = True
                break
            # Busy-wait (spinning). In real-world scenarios, it's better to use sleep to prevent CPU exhaustion.

    def _release_node_lock(self, node):
        node.state_lock = False

    def _update_lock_count_upwards(self, node, delta):
        current = node.parent
        while current:
            # Acquire lock before updating
            self._acquire_node_lock(current)
            current.locked_descendant_count += delta
            self._release_node_lock(current)
            current = current.parent

    def Lock(self, node, uid):
        # Step 1: Acquire lock on the target node
        self._acquire_node_lock(node)

        # Step 2: Check if the node is already locked or has locked descendants
        if node.isLocked or node.locked_descendant_count > 0:
            self._release_node_lock(node)
            return 'false'

        # Step 3: Check if any ancestors are locked
        current = node.parent
        ancestors = []
        while current:
            ancestors.append(current)
            current = current.parent

        ancestors = reversed(ancestors)
        # Acquire locks on all ancestors to prevent changes while checking
        for anc in ancestors:
            self._acquire_node_lock(anc)

        # Verify no ancestors are locked
        for anc in ancestors:
            if anc.isLocked:
                # Release all locks if an ancestor is locked
                for locked_node in ancestors:
                    self._release_node_lock(locked_node)
                self._release_node_lock(node)
                return 'false'

        # Step 4: Lock the node
        node.isLocked = True
        node.uid = uid
        # Update locked_descendant_count for all ancestors
        for anc in ancestors:
            anc.locked_descendant_count += 1

        # Step 5: Release all locks
        for anc in ancestors:
            self._release_node_lock(anc)
        self._release_node_lock(node)

        return 'true'

    def Unlock(self, node, uid):
        self._acquire_node_lock(node)

        if not node.isLocked or node.uid != uid:
            self._release_node_lock(node)
            return 'false'

        node.isLocked = False
        node.uid = None

        # Update locked_descendant_count for all ancestors
        current = node.parent
        while current:
            self._acquire_node_lock(current)
            current.locked_descendant_count -= 1
            self._release_node_lock(current)
            current = current.parent

        self._release_node_lock(node)
        return 'true'

    def Upgrade(self, node, uid):
        self._acquire_node_lock(node)

        if node.isLocked or node.locked_descendant_count == 0:
            self._release_node_lock(node)
            return 'false'

        # Check ancestors
        current = node.parent
        ancestors = []
        while current:
            ancestors.append(current)
            current = current.parent

        for anc in ancestors:
            self._acquire_node_lock(anc)

        # Verify no ancestors are locked
        for anc in ancestors:
            if anc.isLocked:
                for locked_node in ancestors:
                    self._release_node_lock(locked_node)
                self._release_node_lock(node)
                return 'false'

        # Collect all locked descendants
        locked_nodes = []
        stack = [node]
        while stack:
            current = stack.pop()
            self._acquire_node_lock(current)
            if current.isLocked:
                locked_nodes.append(current)
            stack.extend(current.children)
            self._release_node_lock(current)

        if not locked_nodes:
            for anc in ancestors:
                self._release_node_lock(anc)
            self._release_node_lock(node)
            return 'false'

        # Ensure all locked descendants are locked by the same uid
        for ld in locked_nodes:
            if ld.uid != uid:
                for anc in ancestors:
                    self._release_node_lock(anc)
                self._release_node_lock(node)
                return 'false'

        # Unlock all descendants
        for ld in locked_nodes:
            self._acquire_node_lock(ld)
            ld.isLocked = False
            ld.uid = None
            # Update locked_descendant_count for ancestors
            self._update_lock_count_upwards(ld, -1)
            self._release_node_lock(ld)

        # Lock the current node
        node.isLocked = True
        node.uid = uid
        self._update_lock_count_upwards(node, 1)

        # Release all ancestor locks and node lock
        for anc in ancestors:
            self._release_node_lock(anc)
        self._release_node_lock(node)

        return 'true'

    def Process(self, queries):
        res = []
        for q in queries:
            parts = q.strip().split()
            if len(parts) != 3:
                res.append('false')
                continue
            ops, node_name, uid = parts
            uid = int(uid)
            node = self.node_map.get(node_name, None)
            if not node:
                res.append('false')
                continue
            if ops == '1':
                res.append(self.Lock(node, uid))
            elif ops == '2':
                res.append(self.Unlock(node, uid))
            elif ops == '3':
                res.append(self.Upgrade(node, uid))
            else:
                res.append('false') 
        return res

def main():
    n = int(sys.stdin.readline().strip())
    m = int(sys.stdin.readline().strip())
    q = int(sys.stdin.readline().strip())

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

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

    tree = M_Arr_Tree(n, m, name_list)
    res = tree.Process(queries)
    for r in res:
        print(r)

if __name__ == "__main__":
    main()

"""



"""
class ReadWriteLock:
    def __init__(self):
        self.readers = 0        # Number of active readers
        self.writer = False     # Is there an active writer
        self.write_requests = 0 # Number of writers waiting

    def acquire_read(self):
        # Busy-wait until there are no active writers or write requests
        while self.writer or self.write_requests > 0:
            pass  # In practice, use sleep or other wait mechanisms

        self.readers += 1

    def release_read(self):
        self.readers -= 1

    def acquire_write(self):
        self.write_requests += 1

        # Busy-wait until there are no active readers or writers
        while self.readers > 0 or self.writer:
            pass  # In practice, use sleep or other wait mechanisms

        self.write_requests -= 1
        self.writer = True

    def release_write(self):
        self.writer = False

class Node:
    def __init__(self, val):
        self.val = val
        self.uid = None
        self.parent = None
        self.children = []
        self.locked_descendant_count = 0
        self.isLocked = False
        self.lock = ReadWriteLock()  # Each node has its own ReadWriteLock

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

        # Initialize nodes
        for name in name_list:
            node = Node(name)
            self.node_list.append(node)
            self.node_map[name] = node

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

        self.root = self.node_list[0] if self.node_list else None

    def _get_path_to_root(self, node):
        path = []
        current = node
        while current:
            path.append(current)  
            current = current.parent
        return path[::-1]  # Reverse to have root first

    def _release_locks(self, acquired_locks):
        for lock_type, anc in reversed(acquired_locks):
            if lock_type == 'read':
                anc.lock.release_read()
            elif lock_type == 'write':
                anc.lock.release_write()

    def Lock(self, node, uid):
        path = self._get_path_to_root(node)
        acquired_locks = []

        try:
            # Step 1: Acquire read locks on all ancestors (excluding the target node)
            for anc in path[:-1]:
                anc.lock.acquire_read()
                acquired_locks.append(('read', anc))

                if anc.isLocked:
                    # Release all acquired locks before returning
                    self._release_locks(acquired_locks)
                    return 'false'

            # Step 2: Release all read locks before acquiring write locks
            self._release_locks(acquired_locks)
            acquired_locks.clear()

            # Step 3: Re-acquire write locks on all ancestors (excluding the target node) in order
            for anc in path[:-1]:
                anc.lock.acquire_write()
                acquired_locks.append(('write', anc))

            # Step 4: Acquire write lock on the target node
            target = path[-1]
            target.lock.acquire_write()
            acquired_locks.append(('write', target))

            # Step 5: Check if the target node is already locked or has locked descendants
            if target.isLocked or target.locked_descendant_count > 0:
                self._release_locks(acquired_locks)
                return 'false'

            # Step 6: Lock the node
            target.isLocked = True
            target.uid = uid

            # Step 7: Update locked_descendant_count for all ancestors
            for anc in path[:-1]:
                anc.locked_descendant_count += 1

            return 'true'
        finally:
            # Step 8: Release all locks
            self._release_locks(acquired_locks)

"""
"""
please generate all possible qs the interviwer may ask i nthe related to threadsafe part only genreate all