Description

In this problem, you are required to write a program that support eight string manipulation commands: insert, insert_front, insert_back, delete, delete_front, delete_back, reverse, and print. Your program should start with an empty string. The details of each command are as follows:

1. insert CHAR POS
   Insert a character CHAR (only be one of 0-9, a-z, A-Z) at the POS (POS <= 2 * 10⁹) position (0-index) of the string (it is guaranteed that POS will not be larger than the current string length). If the position is currently taken, push the existing characters to the right. It is guaranteed that the sum of POS of all "insert" commands will not exceed 4 * 10⁶.
   
   For example, if the commands are:
       insert a 0
       insert 1 0
       insert c 1
       insert x 3
   Then the transition of the string for each of the command will be: “” (i.e. empty string) => “a” => “1a” => “1ca” => “1cax”.
   
    
2. insert_front CHAR
   Insert a character CHAR at the front of the string. It is effectively equal to insert CHAR 0. CHAR can only be one of 0-9, A-Z and a-z.
   
    
3. insert_back CHAR
   Insert a character CHAR at the end of the string. It is effectively equal to insert CHAR CURRENT_STR_LEN. CHAR can only be one of 0-9, A-Z and a-z.
   
    
4. delete POS
   Delete a character at the POS position (0-index) of the string (it is guaranteed that POS will not be equal to or larger than the current string length). It is guaranteed that the sum of POS of all "delete" commands will not exceed 4 * 10⁶.
   
   For example, if the commands are:
       insert a 0
       insert 1 0
       insert c 1
       delete 1
   Then the transition of the string for each of the command will be: “” (i.e. empty string) => “a” => “1a” => “1ca” => “1a”.
   
    
5. delete_front
   Delete a character at the front of the string. When the string is non-empty, it is effectively equal to delete 0. If the string is empty, ignore the command.
   
    
6. delete_back
   Delete a character at the end of the string. When the string is non-empty, it is effectively equal to delete CHAR CURRENT_STR_LEN-1. If the string is empty, ignore the command.
   
    
7. reverse
   Reverse the order of all characters in the string.
   
   For example, if the commands are:
       insert a 0
       insert 1 0
       reverse
       insert 1 1
       reverse
   Then the transition of the string for each of the command will be: “” (i.e. empty string) => “a” => “1a” => “a1” => “a11” => "11a".
   
    
8. print
   Print the current string on a new line.
   
   For example, if the commands are:
       insert a 0
       insert 1 0
       print
       reverse
       insert b 2
       print
   Then you should print out:
       1a
       a1b

Your program MUST be in either C or C++. Your program MAY include <string>, <iostream>, <cassert>, <cstdio>, and <cstdlib> (and their C counterpart if any). You MUST NOT include any other C/C++ standard library headers.

Input

The first line containing the number of commands to be processed M (0 < M <= 10⁶), with the commands starting on the next line, one command per line.

 

Output

The content printed out by the print command(s).

Sample Input  Download

Sample Output  Download

Discuss