Spreadsheet Undo/Redo Operations

Design a data structure that simulates Undo/Redo functionality for a simplified spreadsheet editor.

A user performs a sequence of operations on cells, where each operation changes the value of a single cell.

Operations

• SET cell value: Sets the specified cell (e.g., "A1") to a given value (which can be a string or a number).
• UNDO k: Undoes the last k successful SET operations. If fewer than k operations are available to undo, all available SET operations are undone.
• REDO k: Redoes the last k operations that were previously undone. If fewer than k operations are available to redo, all available undone operations are redone.

Rules

• UNDO and REDO operations exclusively affect SET operations.
• Executing a new SET operation after an UNDO operation will clear the entire redo history.
• If an UNDO k command requests more steps than currently exist in the undo history, all available steps should be undone.
• If a REDO k command requests more steps than currently exist in the redo history, all available steps should be redone.

Input/Output

Given a list of commands, the system should process them and return the final mapping of cell -> value representing the state of the spreadsheet.

Example

Consider the following sequence of commands:

1. SET A1 10
2. SET A1 20
3. SET B2 5
4. UNDO 2 (This undoes B2=5, then A1=20. The state before this SET A1 20 was A1=10.)
5. REDO 1 (This redoes A1=20.)
6. SET C1 7 (This clears the redo history.)

The final state of the spreadsheet should be: A1=20, C1=7. Cell B2 would be empty.

Constraints

• The total number of commands (N) can be up to 10^5.
• The solution should aim for efficient time and memory complexity per command.
• Candidates are expected to discuss data structures and complexity, then implement the core logic.