guanine

Problem Description

Guan has just learnt the four nucleobases in DNA: Adenine, Thymine, Cytosine and Guanine. Wait, GUANine. Guan is incredibly intrigued by this based named GUANine. "Was it named after me?" he thought to himself. "Surely it must be, I am so smart." After countless hours of searching Google for the origins of Guanine, his search turned out futile. There was no results found for "Wu Guanqun's brilliant discovery of new nucleobase Guanine." Devastated, he turns back to his lego DNA play set and starts constructing DNA sequences.

"ATTGCCGATTGACT," Guan made, "hmm, gene for awkwardness."

"GCTAGCTAGCGCGTAT," Guan made another gene sequence, "hmm, gene for being weird."

Guan starts off with an empty DNA string. He can then choose any one of four operations to do:

1. "ADD_BACK x": add nucleotide with base x at the back of the DNA sequence,
2. "ADD_FRONT x": add nucleotide with base x at the front of the DNA sequence,
3. "SNIP_BACK y": cut the DNA between nucleotide y and nucleotide y+1 (0-indexed) and keep the front segment,
4. "SNIP_FRONT y": cut the DNA between nucleotide y and nucleotide y+1 (0-indexed) and keep the back segment.

At any point in time, Guan can also have a "QUERY z" operation, which requires you to output the z-th nucleobase from the front. (0-indexed)

Guan can conduct up to N operations and queries in total. Each query/operation will be in the form "<command> <parameter>". Output only in a "QUERY" operation.

Subtasks

Subtask 1 (11%): 1 ≤ N ≤ 100. There will only be ADD_BACK and QUERY operations.
Subtask 2 (13%): 1 ≤ N ≤ 100. There will be no SNIP operations.
Subtask 3 (15%): 1 ≤ N ≤ 100.
Subtask 4 (20%): 1 ≤ N ≤ 1000.
Subtask 5 (41%): 1 ≤ N ≤ 300000.

Input

The first line of input will contain one integer, N.
The next N lines of input will contain one string and one integer/character, representing the operation.

Output

For each query operation, your program should output one upper-case character representing the nucleobase and a newline.

Sample Input 1

9
ADD_BACK C
ADD_FRONT A
ADD_BACK T
ADD_FRONT A
QUERY 2
SNIP_FRONT 1
ADD_FRONT G
QUERY 0
QUERY 2

Sample Output 1

C
G
T