Final String After Undo/Redo

You are given an array of strings commands to process in order, starting from an empty text. Each command is one of:

• "type x" means append the single lowercase letter x to the end of the text. This also clears the redo history.
• "undo" means remove the last character of the text. If the text is empty, this does nothing.
• "redo" means re-append the most recently undone character that has not already been reapplied. If there is no such character (nothing was undone, or typing has cleared the redo history), this does nothing.

Return the text after all commands have been processed. The result may be the empty string.

Examples

Example 1

Input: commands = ["type a", "type b", "undo", "redo", "type c"]
Output: "abc"
Explanation: After "type a" and "type b" the text is "ab". "undo" removes 'b' ("a"), "redo" restores it ("ab"), and "type c" appends 'c' ("abc").

Example 2

Input: commands = ["type a", "type b", "type c", "undo", "undo", "type d"]
Output: "ad"
Explanation: After the three type commands the text is "abc". The two undos remove 'c' and 'b' ("a"). "type d" appends 'd' and clears the redo history, so 'b' and 'c' can no longer be restored.