Undo and redo

commands holds, in order, the commands given to a text box. The command "type <word>" (for example, "type hi") adds the word to the end of the text, with no space before it. "undo" removes the most recently added word that is still in the text and sets it aside. "redo" takes the word that was set aside most recently and adds it back to the end of the text.

When a new type command is given, all the words set aside are thrown away. If there is no word to remove, undo does nothing, and if no word is set aside, redo does nothing. Complete the function solution, which returns the text after all the commands have been run. If the text is empty, return an empty string "".

Function

solution(commands)

Constraints

• The length of commands is from 1 to 200,000.
• Each command is "undo", "redo", or "type" followed by a space and a word. Each word is made of lowercase English letters, with a length from 1 to 10.

Examples

Starter code

def solution(commands):
    answer = ""
    return answer