Deloitte | COGNIZANT | IBM | CAPGEMINI

import sys sys.setrecursionlimit(1_000_000) data = sys.stdin.read().strip().splitlines() it = iter(data) N = int(next(it)) m = int(next(it)) Q = int(next(it)) names = [next(it).strip() for _ in range(N)] idx = {name: i for i, name in enumerate(names)} parent = [-1] * N children = [[] for _ in range(N)] for i in range(1, N): p = (i - 1) // m parent[i] = p children[p].append(i) locked_by = [None] * N locked_desc_count = [0] * N def has_locked_ancestor(u: int) -> bool: v = parent[u] while v != -1: if locked_by[v] is not None: return True v = parent[v] return False def add_to_ancestors(u, delta): v = parent[u] while v != -1: locked_desc_count[v] += delta v = parent[v] def lock(u, uid): if locked_by[u] is not None: return False if locked_desc_count[u] > 0: return False if has_locked_ancestor(u): return False locked_by[u] = uid add_to_ancestors(u, 1) return True def unlock(u, uid): if locked_by[u] != uid: return False locked_by[u] = None add_to_ancestors(u, -1) return True def upgrade(u, uid): if locked_by[u] is not None: return False if has_locked_ancestor(u): return False if locked_desc_count[u] == 0: return False stack = [u] locked_nodes = [] ok_uid = uid while stack: x = stack.pop() if locked_desc_count[x] == 0 and locked_by[x] is None: continue for c in children[x]: if locked_desc_count[c] > 0 or locked_by[c] is not None: stack.append(c) if x != u and locked_by[x] is not None: locked_nodes.append(x) if locked_by[x] != ok_uid: return False for x in locked_nodes: locked_by[x] = None add_to_ancestors(x, -1) locked_by[u] = uid add_to_ancestors(u, 1) return True out = [] for _ in range(Q): parts = next(it).spli