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:
- "ADD_BACK c x": add c nucleotides with base x at the back of the DNA sequence,
- "ADD_FRONT c x": add c nucleotides with base x at the front of the DNA sequence,
- "SNIP_BACK y": cut the DNA between nucleotide y and nucleotide y+1 (0-indexed) and keep the front segment,
- "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
For all subtasks, 1 ≤ c ≤ 2
31 - 1. All indices in the input will be valid (i.e. less than the length of the DNA string).
Subtask 1 (11%): 1 ≤ N ≤ 100.
c will always be 1.
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.
Subtask 6 (0%): Sample Testcases
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 1 C
ADD_FRONT 1 A
ADD_BACK 1 T
ADD_FRONT 1 A
QUERY 0
SNIP_FRONT 1
ADD_FRONT 1 G
QUERY 0
QUERY 0
Sample Output 1
A
G
G