The eVIgma Text Editor

In order to not only write code for problems, we decided to build a fully functional text editor, e-VI-gma! For every feature you implement you will receive extra points, which will vary depending on how efficiently the feature works.

First feature: Typewriter

Initially, we can only insert characters at the end of the text and delete the last character. However, since we do not have a full view of the text we are writing, we can request to print the ~i~-th character of the text.

Second feature: Backups

Now, besides insertions and deletions, we can create backups of our work. These backups are mutable, meaning that every insertion/deletion can be performed at the end of any copy of the text we have.

Third feature: Finally we have arrow keys!

The typewriter has been modernized and now allows us to move within the file to perform insertions and deletions anywhere! Unfortunately, the backup system stopped working, so while we are trying to fix it, it is enough to support insertions and deletions at any position in the file.

Fourth feature: We fixed the backups!

Everything works now! We can write and delete at any position of any copy of the file.

Input Format (STDIN)

First, an integer ~Q~ is given: the number of operations that will be performed on the file. Then ~Q~ lines follow, each describing one operation:

1. INSERT i s: inserts the string s at position ~i~ in the current version (initially we are at version 1). (For example, for the first 2 features, ~i~ will always be equal to ~L + 1~, where ~L~ is the current length of the version.)
2. ERASE i k: deletes ~k~ characters starting from position ~i~ in the current version.
3. GET i v: prints the ~i~-th character (1-indexed) of version ~v~
4. SNAP: a new version which is a copy of the current one, with number \(\hbox{|current versions|} + 1\)
5. VERSION v: sets version ~v~ as the current version.

Output Format (STDOUT)

Print a single line consisting of characters: for every GET query, output the corresponding character.

Constraints

• For ~30\%~ of the test cases, ~Q \le 500~
• For the remaining ~70\%~, ~Q \le 5,000~
• For ~50\%~ of the test cases, the maximum string length will be ~{} \le 5,100~
• For the remaining ~50\%~, ~|S| \le 100,000~

Example

Input:

5
INSERT 1 abcde
SNAP
ERASE 3 2
GET 3 1
GET 3 2

Output:

ec