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").