Most Frequent Function in Call Stacks by Thread

Problem: Find the Most Frequent Function in Call Stacks by Thread You are given multiple sampled function call stacks. Each call stack belongs to one thread and is ordered from the outermost call to the innermost call. For example: main A B means main called A, and A called B. The depth of main is 0, A is at depth 1, and B is at depth 2. For each thread, find the function that appears most frequently in that thread's call stacks. Counting Rules For each thread: Each occurrence of a function in a call stack contributes +1 to its count. If the same function appears multiple times in the same stack due to recursion, count every occurrence. If multiple functions have the same count, return the function whose maximum observed depth is deeper. If both count and maximum depth are tied, return the lexicographically smallest function name to make the result deterministic. Input Format n thread_id_1 k_1 func_1 func_2 ... func_k1 thread_id_2 k_2 func_1 func_2 ... func_k2 ... thread_id_n k_n func_1 func_2 ... func_kn n is the number of sampled call stacks. Each following line represents one call stack: thread_id: thread ID, a string without spaces. k: number of functions in this stack. Followed by k function names, each without spaces. Output Format For each thread, output one line: thread_id most_frequent_function Threads should be output in lexicographical order of thread_id. Constraints 1 <= n <= 10^5 1 <= k <= 10^3 Total number of function occurrences across all call stacks is at most 10^6 Length of each thread_id and function name is at most 100 Example Input 3 t1 3 main A B t1 3 main A C t1 3 main A B Output t1 A