Design paint editor with undo/redo

Implement a simplified `Paint` editor that supports drawing on a 2D canvas and reverting changes using undo and redo operations. ### Canvas You are given a 2D grid representing a canvas. Each cell can store: - a color value (string or integer), or - `None` for an empty cell. You will initialize the canvas with a given width and height. Assume coordinates are zero-based and given as `(x, y)` where `x` is the column index and `y` is the row index. Coordinates are guaranteed to be within bounds. ### Required Operations You must design and implement a `Paint` class with the following methods: 1. `draw(x, y, color)` - Set the pixel at position `(x, y)` to the given `color`. 2. `erase(x, y)` - Remove whatever color is at `(x, y)` and set it back to empty (`None`). 3. `fill(x, y, color)` - Perform a flood fill operation starting at `(x, y)`: - Let `orig` be the color currently at `(x, y)`. - Replace the pixel at `(x, y)` with `color`. - Recursively replace any adjacent cells (up, down, left, right) that have color `orig` with `color`. - Stop expanding when encountering a different color or the canvas boundary. - If `orig` is already equal to `color`, the operation may be a no-op. 4. `undo()` - Revert the canvas to the state **before** the most recent modifying operation (`draw`, `erase`, or `fill`). - If there is no operation to undo, this may be a no-op. 5. `redo()` - Re-apply the most recently undone operation, restoring the canvas to the state after that operation. - If there is no operation to redo, this may be a no-op. ### Behavior Rules - Any operation that modifies the canvas (`draw`, `erase`, `fill`) should become an undoable action. - Calling `undo()` moves the current state into a redo history so that it can be restored with `redo()`. - Calling `redo()` re-applies that state and moves it back into the undo history. - After performing a new modifying operation (`draw`, `erase`, `fill`), the redo history must be cleared. - All operations should be deterministic and consistent. ### Requirements - Design and implement the `Paint` class and its methods. - You may choose any reasonable data structures for representing: - The canvas. - Undo and redo histories. - Your implementation must correctly maintain canvas state, undo/redo history, and fill behavior. Assume reasonable constraints, e.g., canvas up to a few thousand by a few thousand cells and up to tens of thousands of operations.