Sparse canvas painting with undo and redo

Implement an unbounded canvas where paint(x, y, color) sets a pixel, read(x, y) returns its color (0 if never painted), undo() reverts the latest paint not yet undone, and redo() reapplies the latest undone paint. A new paint clears the redo history, and undo or redo with nothing to act on does nothing. Store only painted pixels, and keep each paint's previous color so undo is O(1).