You are given an **infinite 2D grid** with integer coordinates. From a cell `(x, y)` you may move in **4 directions** (North/South/East/West) by 1 cell per move. You are given: - `start = (sx, sy)` - `goal = (gx, gy)` - A finite set of **static barriers** `blocked`, where each coordinate in `blocked` is permanently impassable. ## Part 1 (static obstacles) Return **any one shortest valid path** from `start` to `goal` as a list of coordinates (or directions). If no path exists, return “unreachable”. Important: the grid is infinite. A naive BFS that expands forever must be avoided; your algorithm should **terminate** even when `goal` is unreachable (e.g., `goal` is fully enclosed by barriers). ## Part 2 (moving parades) Now, in addition to `blocked`, you are given a list of moving obstacles called **parades**. Each parade has: - an initial position `(px, py)` at time `t = 0` - a direction in `{N, S, E, W}` - it moves **one cell in its direction every 2 seconds** (i.e., it changes position at times `t = 2, 4, 6, ...`; it stays in place at `t = 0, 1`, then moves for `t = 2, 3`, etc.). Rules: - You still move once per second (at integer times). Optionally, you may also **wait in place** for 1 second. - You may never be on a cell that is a static barrier. - You may never be on a cell occupied by any parade at that time. If a move would place you onto a parade’s position at time `t+1`, that move is invalid. Return any **minimum-time** valid path from `start` at `t=0` to `goal` (with timestamps implied by step index), or “unreachable”. As in Part 1, the grid is infinite; ensure your approach does not run forever when the destination cannot be reached.