Text Editor With Undo

Build a TextEditor class with a cursor, undo and redo. Every method returns the text with a | showing where the cursor is, for example 'ab|c'. The | is only for display and is never part of the text.

• TextEditor() starts empty, with the cursor at the start.
• write(s) inserts s at the cursor; the cursor ends up after the inserted text.
• backspace(k) deletes up to k characters to the left of the cursor (fewer if the cursor is near the start).
• left(k) and right(k) move the cursor up to k places; it stops at either end.
• undo() puts the text and the cursor back exactly as they were before the most recent change that has not been undone. With nothing to undo, it does nothing.
• redo() takes back the most recent undo: the text and cursor return to how they were when that undo was used. A new change clears everything that could be redone.

Only write and backspace are changes, and only when they really change the text: writing '' or deleting at the very start does not count. Cursor moves are never undone.

Examples

ed = TextEditor()
ed.write('hello')    # returns 'hello|'
ed.left(2)           # returns 'hel|lo'
ed.write('p')        # returns 'help|lo'
ed.backspace(10)     # returns '|lo'
ed.undo()            # returns 'help|lo'
ed.undo()            # returns 'hel|lo'
ed.redo()            # returns 'help|lo'

Constraints

• Up to 5,000 calls, and the text stays under 10,000 characters
• s never contains |