Implement snake game and find org LCA

Part A — Snake Game Engine: Implement a grid-based snake game. The board has height H and width W (0-indexed, row-major). The snake starts at (0, 0) moving right and initially occupies one cell. You are given a list of food positions as (row, col) that must be consumed in order. Expose an API: class Snake(int H, int W, List<(int,int)> food); int step(char dir) where dir ∈ {'U','D','L','R'}. On each step, the snake advances one cell; if the new head lands on the next food, increase score by 1 and grow (do not remove tail this turn); otherwise move the tail forward (no growth). Return the current score after a valid move, or -1 if the snake collides with walls or its own body (moving into the cell just vacated by the tail in the same step is allowed). Design data structures to support O( 1) time per step and implement the API. Describe time/space complexity. Part B — Lowest Common Manager: Given an organization chart as a rooted n-ary tree with unique employee IDs and only child adjacency lists (no parent pointers), implement a function lowestCommonManager(root, a, b) that returns the lowest common manager of employees a and b. Handle cases where one or both employees may be absent. Discuss an approach optimized for a single query and an approach that supports many queries efficiently (e.g., preprocessing). Provide time/space complexity for both.