Implement a simple text editor. The editor initially contains an empty string, $\mbox{S}$. Perform $Q$ operations of the following $\begin{array}{c}4\end{array}$ types:  

append$\left(\mbox{W}\right)$  - Append string $\mbox{w}$ to the end of $\mbox{S}$.
delete$\left(k\right)$   - Delete the last $\boldsymbol{\mbox{k}}$ characters of $\mbox{S}$.
print$\left(k\right)$     - Print the $k^{th}$ character of $\mbox{S}$.
undo$\left(\right)$     - Undo the last (not previously undone) operation of type $1$ or $2$, reverting $\mbox{S}$ to the state it was in prior to that operation.  

Example   

$S=\textbf{'abcde'}$ 

$ops=[\text{''1}\:\:\textsf{fg'},\:\:\text{'3}\:\text{6'},\:\:\text{'2}\:\text{5'},\:\:\text{'4'},\:\:\text{''3}\:\text{7'},\:\:\text{'4'},\:\:\text{'3}\:\text{4'}]$   

operation
index   S       ops[index]  explanation
-----   ------  ----------  -----------
0       abcde   1 fg        append fg
1       abcdefg 3 6         print the 6th letter - f
2       abcdefg 2 5         delete the last 5 letters
3       ab      4           undo the last operation, index 2
4       abcdefg 3 7         print the 7th characgter - g
5       abcdefg 4           undo the last operation, index 0
6       abcde   3 4         print the 4th character - d

The results should be printed as:  

f
g
d

Input Format

The first line contains an integer, $Q$, denoting the number of operations. 

Each line $\boldsymbol{i}$ of the $Q$ subsequent lines (where $0\leq i<Q$) defines an operation to be performed. Each operation starts with a single integer, $\boldsymbol{\boldsymbol{t}}$ (where $t\in\{1,2,3,4\}$), denoting a type of operation as defined in the Problem Statement above. If the operation requires an argument, $\boldsymbol{\boldsymbol{t}}$ is followed by its space-separated argument. For example, if $t=1$ and $W=\text{"abcd"}$, line $\boldsymbol{i}$ will be 1 abcd. 

Constraints

$1\leq Q\leq10^6$  
$1\leq k\leq|S|$  
The sum of the lengths of all $\mbox{w}$ in the input $\leq10^{6}$.  
The sum of $\boldsymbol{\mbox{k}}$ over all delete operations $\leq2\cdot10^{6}$.  
All input characters are lowercase English letters.  
It is guaranteed that the sequence of operations given as input is possible to perform.

Output Format

Each operation of type $3$ must print the $k^{th}$ character on a new line.

Sample Input
STDIN   Function
-----   --------
8       Q = 8
1 abc   ops[0] = '1 abc'
3 3     ops[1] = '3 3'
2 3     ...
1 xy
3 2
4 
4 
3 1

Sample Output
c
y
a

Explanation

Initially, $\mbox{S}$ is empty. The following sequence of $8$ operations are described below:

$S=\text{"}$. We append $\boldsymbol{abc}$ to $\mbox{S}$, so $S=\text{"}abc"$. 
Print the $3^{rd}$ character on a new line. Currently, the $3^{rd}$ character is c.
Delete the last $3$ characters in $\mbox{S}$ ($\boldsymbol{abc}$), so $S=\text{"}$. 
Append $x_y$ to $\mbox{S}$, so $S=\text{"}xy\text{"}$. 
Print the $2^{nd}$ character on a new line. Currently, the $2^{nd}$ character is y.
Undo the last update to $\mbox{S}$, making $\mbox{S}$ empty again (i.e., $S=\text{"}$).
Undo the next to last update to $\mbox{S}$ (the deletion of the last $3$ characters), making $S=\text{"abc"}$.
Print the $1^{st}$ character on a new line. Currently, the $1^{st}$ character is a.

Difficulty: MEDIUM
Tags: Data structures
Skill types: Data structures

Starter code:

Solutions:
q = int(input())
stack = ['']
for _ in range(q):
	(o_type, *par) = input().split()
	o_type = int(o_type)
	if o_type in (1, 2, 3):
		par = par[0]
		if o_type in (2, 3):
			par = int(par)
	if o_type == 1:
		stack.append(stack[-1] + par)
	elif o_type == 2:
		stack.append(stack[-1][:-par])
	elif o_type == 3:
		print(stack[-1][par - 1])
	elif o_type == 4:
		stack.pop()


Q = int(input().strip())
S = ''
st = []
for q in range(Q):
	tks = input().strip().split(' ')
	o = int(tks[0])
	if o == 1:
		p = tks[1]
		S = S + p
		st.append([2, len(p)])
	elif o == 2:
		p = int(tks[1])
		st.append([1, S[-p:]])
		S = S[:-p]
	elif o == 3:
		print(S[int(tks[1]) - 1])
	elif o == 4:
		(o, p) = st.pop()
		if o == 1:
			S = S + p
		elif o == 2:
			S = S[:-p]


num_op = int(input())
string_stack = []
op_stack = []
for _ in range(num_op):
	new_op = input().split()
	op = int(new_op[0])
	arg = ''
	if len(new_op) > 1:
		if op == 1:
			arg = new_op[1]
		else:
			arg = int(new_op[1])
	if op == 1:
		for char in arg:
			string_stack.append(char)
		op_stack.append((op, len(arg)))
	elif op == 2:
		erased = string_stack[len(string_stack) - arg:]
		for _ in range(arg):
			string_stack.pop()
		op_stack.append((op, erased))
	elif op == 3:
		print(string_stack[arg - 1])
	elif op == 4:
		prev = op_stack.pop()
		prev_op = prev[0]
		if prev_op == 1:
			for _ in range(prev[1]):
				string_stack.pop()
		elif prev_op == 2:
			for char in prev[1]:
				string_stack.append(char)


h = []
s = ''
o = int(input())
for z in range(o):
	usr = input().split()
	h.append([usr[0], s])
	if usr[0] == '1':
		s = s + usr[1]
	elif usr[0] == '2':
		s = s[:len(s) - int(usr[1])]
	elif usr[0] == '3':
		print(s[int(usr[1]) - 1])
	else:
		while h[-1][0] == '3' or h[-1][0] == '4':
			h.pop()
		s = h[-1][1]
		h.pop()


ops = int(input())
stack = []
myStr = ''
for i in range(ops):
	op = input().split(' ')
	if op[0] == '1':
		myStr = myStr + op[1]
		stack.append((2, len(op[1])))
	if op[0] == '2':
		n = int(op[1])
		removed = myStr[-n:]
		myStr = myStr[:-n]
		stack.append((1, removed))
	if op[0] == '3':
		print(myStr[int(op[1]) - 1])
	if op[0] == '4':
		rev = stack.pop()
		if rev[0] == 1:
			myStr = myStr + rev[1]
		else:
			n = int(rev[1])
			myStr = myStr[:-n]


class ArrayStack(object):

	def __init__(self):
		self._data = []

	def __len__(self):
		return len(self._data)

	def push(self, item):
		self._data.append(item)

	def is_empty(self):
		return len(self._data) == 0

	def top(self):
		if self.is_empty():
			raise Empty('stack is empty')
		return self._data[-1]

	def pop(self):
		if self.is_empty():
			raise Empty('stack is empty')
		return self._data.pop()

class TextEditor(object):

	def __init__(self):
		self._contents = []
		self._s = ArrayStack()

	def _stack_it(self):
		self._s.push(''.join(self._contents))

	def append(self, element):
		self._stack_it()
		self._contents += list(element)

	def erase(self, k):
		self._stack_it()
		self._contents = self._contents[:-k]

	def get(self, k):
		return self._contents[k - 1]

	def undo(self):
		if not self._s.is_empty():
			top = self._s.pop()
			self._contents = list(top)
try:
	n = int(input())
except ValueError:
	print('Not a number')
editor = TextEditor()
while n > 0:
	query = input()
	if query.find(' ') != -1:
		(cmd, item) = query.split(' ', 1)
		if cmd == '1':
			editor.append(item)
		elif cmd == '2':
			editor.erase(int(item))
		elif cmd == '3':
			print(editor.get(int(item)))
	elif query == '4':
		editor.undo()
	n -= 1


class ArrayStack(object):

	def __init__(self):
		self._data = []

	def __len__(self):
		return len(self._data)

	def push(self, item):
		self._data.append(item)

	def is_empty(self):
		return len(self._data) == 0

	def top(self):
		if self.is_empty():
			raise Empty('stack is empty')
		return self._data[-1]

	def pop(self):
		if self.is_empty():
			raise Empty('stack is empty')
		return self._data.pop()

class TextEditor(object):

	def __init__(self):
		self._contents = []
		self._s = ArrayStack()

	def _stack_it(self):
		self._s.push(''.join(self._contents))

	def append(self, element):
		self._stack_it()
		self._contents += list(element)

	def erase(self, k):
		self._stack_it()
		self._contents = self._contents[:-k]

	def get(self, k):
		return self._contents[k - 1]

	def undo(self):
		if not self._s.is_empty():
			top = self._s.pop()
			self._contents = list(top)
try:
	n = int(input())
except ValueError:
	print('Not a number')
editor = TextEditor()
while n > 0:
	query = input()
	if query.find(' ') != -1:
		(cmd, item) = query.split(' ', 1)
		if cmd == '1':
			editor.append(item)
		elif cmd == '2':
			editor.erase(int(item))
		elif cmd == '3':
			print(editor.get(int(item)))
	elif query == '4':
		editor.undo()
	n -= 1


Q = int(input())
newS = S = ''
stack = []
for _ in range(Q):
	query = input().split()
	if query[0] == '1':
		newS = S + query[1]
		stack.append(S)
	elif query[0] == '2':
		K = int(query[1])
		newS = S
		while K:
			newS = newS[:-1]
			K -= 1
		stack.append(S)
	elif query[0] == '3':
		K = int(query[1]) - 1
		print(S[K])
	else:
		newS = stack.pop()
	S = newS


Q = int(input())
S = ''
stack = []
for _ in range(0, Q):
	t = input().split()
	ops = int(t[0])
	if ops == 1:
		val = t[1]
		S += val
		stack.append([ops, len(val)])
	elif ops == 2:
		k = int(t[1])
		erased = S[-k:]
		S = S[:-k]
		stack.append([ops, erased])
	elif ops == 3:
		K = int(t[1]) - 1
		print(S[K])
	else:
		l = stack.pop()
		if int(l[0]) == 1:
			S = S[:-l[1]]
		else:
			S += l[1]


q = int(input())
s1 = ''
s2 = []
for i in range(q):
	n = list(input().split())
	x = int(n[0])
	if x == 1:
		s2.append(s1)
		s1 += n[1]
	elif x == 2:
		s2.append(s1)
		s1 = s1[0:len(s1) - int(n[1])]
	elif x == 3:
		print(s1[int(n[1]) - 1])
	else:
		s1 = s2.pop()


Q = int(input())
undoStack = []
S = ''
for _ in range(Q):
	operation = input().split()
	op = int(operation[0])
	if op == 1:
		undoStack.append((op, operation[1]))
		S += operation[1]
	elif op == 2:
		undoStack.append((op, S[-int(operation[1]):]))
		S = S[:-int(operation[1])]
	elif op == 3:
		print(S[int(operation[1]) - 1])
	elif op == 4:
		undo = undoStack.pop()
		if undo[0] == 1:
			S = S[:-len(undo[1])]
		else:
			S += undo[1]


def append(string, word, stack):
	stack.append('2' + str(len(word)))
	string = string + word
	return string

def delete(string, num, stack):
	chars = string[len(string) - num:]
	stack.append('1' + chars)
	string = string[:len(string) - num]
	return string
numInputs = int(input())
string = ''
stack = []
for i in range(numInputs):
	ins = input()
	op = ins.split(' ')
	operator = op[0]
	if operator == '1':
		word = op[1]
		stack.append(string)
		string = string + word
	elif operator == '2':
		num = int(op[1])
		chars = string[len(string) - num:]
		stack.append(string)
		string = string[:len(string) - num]
	elif operator == '3':
		print(string[int(op[1]) - 1])
	if operator == '4' and stack:
		string = stack.pop()


stack = ['']
ops = int(input())
for _ in range(ops):
	inp = input().split()
	op = int(inp[0])
	if op == 1:
		stack.append(stack[len(stack) - 1] + inp[1])
	elif op == 2:
		k = int(inp[1])
		stack.append(stack[len(stack) - 1][:-k])
	elif op == 3:
		k = int(inp[1])
		print(stack[len(stack) - 1][k - 1])
	elif op == 4:
		stack.pop()


from collections import deque
q = int(input())
s = ''
stack_undone = deque()
for i in range(q):
	line = input().strip().split(' ')
	c = line[0]
	k = line[1] if len(line) > 1 else 0
	if c is '1':
		stack_undone.append(s)
		s += k
	elif c is '2':
		stack_undone.append(s)
		s = s[:len(s) - int(k)]
	elif c is '3':
		print(s[int(k) - 1], end='\n')
	else:
		s = stack_undone.pop()


class Stack:

	def __init__(self):
		self.data = []

	def push(self, data):
		self.data.append(data)

	def pop(self):
		if self.data:
			return self.data.pop()
		else:
			return None

	def peek(self):
		return self.data[len(self.data) - 1]

	def size(self):
		return len(self.data)

class TextEditor:

	def __init__(self):
		self.text = Stack()
		self.undo_stack = Stack()

	def parse_instruction(self, instruction):
		i = instruction.split(' ')
		if int(i[0]) == 1:
			for char in i[1]:
				self.append(char)
			self.undo_stack.push(instruction)
		elif int(i[0]) == 2:
			erstr = self.erase(int(i[1]))
			self.undo_stack.push(erstr)
		elif int(i[0]) == 3:
			return self.get(int(i[1]))
		elif int(i[0]) == 4:
			self.undo()

	def append(self, w):
		self.text.push(w)

	def erase(self, k):
		erstr = ''
		for i in range(k):
			erstr += self.text.pop()
		erstr_rev = '2 '
		for i in range(len(erstr) - 1, -1, -1):
			erstr_rev += erstr[i]
		return erstr_rev

	def get(self, k):
		s = self.text.size()
		num_to_undo = s - k
		counter = 0
		undo_stack = Stack()
		while counter < num_to_undo:
			undo_stack.push(self.text.pop())
			counter += 1
		ret_val = self.text.peek()
		while counter > 0:
			self.text.push(undo_stack.pop())
			counter -= 1
		print(ret_val)

	def undo(self):
		reperform = self.undo_stack.pop().split(' ')
		if int(reperform[0]) == 1:
			for i in range(len(reperform[1])):
				self.text.pop()
		elif int(reperform[0]) == 2:
			for i in range(len(reperform[1])):
				self.text.push(reperform[1][i])
n = int(input().strip())
t = TextEditor()
for i in range(n):
	instr = input().strip()
	t.parse_instruction(instr)


S = ''
SList = []
Q = int(input())
i = 1
SList.append('')
while i <= Q:
	i = i + 1
	op = input().split()
	if op[0] == '1':
		SList.append(S)
		S = S + op[1]
	elif op[0] == '2':
		SList.append(S)
		S = ''.join(S.split())[:-1 * int(op[1])]
	elif op[0] == '3':
		print(S[int(op[1]) - 1])
	elif op[0] == '4':
		S = SList.pop()


class Stack:

	def __init__(self):
		self.items = []

	def is_empty(self):
		return self.items == []

	def push(self, item):
		self.items.append(item)

	def pop(self):
		return self.items.pop()

	def peek(self):
		return self.items[-1]

	def size(self):
		return len(self.items)

class TextEditor:

	def __init__(self):
		self.letters = []

	def append(self, w):
		self.letters += list(w)
		return self.letters

	def erase(self, k):
		del self.letters[len(self.letters) - k:]
		return self.letters

	def get(self, index):
		return self.letters[index - 1]

def manipulate_text():
	s = Stack()
	letters = []
	q = int(input().strip())
	for i in range(q):
		op = input().strip().split()
		if op[0] == '1':
			letters = [] if s.is_empty() else s.peek()
			s.push(letters + list(op[1]))
		elif op[0] == '2':
			letters = s.peek()
			letters = letters[:-int(op[1])]
			s.push(letters)
		elif op[0] == '3':
			letters = s.peek()
			print(letters[int(op[1]) - 1])
		elif op[0] == '4':
			s.pop()
manipulate_text()


N = int(input().strip())
S = []
op_stack = []
for i in range(N):
	inn = input().strip().split()
	if inn[0] == '1':
		S.extend(list(inn[1]))
		op_stack.append(['1', inn[1]])
	elif inn[0] == '2':
		removed = S[-int(inn[1]):]
		S = S[:-int(inn[1])]
		op_stack.append(['2', removed])
	elif inn[0] == '3':
		print(S[int(inn[1]) - 1])
	else:
		[oper, val] = op_stack.pop()
		if oper == '1':
			S = S[:-len(val)]
		else:
			S += val


def append(s, chars):
	s.extend(chars)

def delete(s, numberOfChars):
	del s[-numberOfChars:]
n = int(input())
s = []
undo = []
for i in range(0, n):
	op = input().strip().split(' ')
	if op[0] == '1':
		chars = list(op[1])
		undo.append([delete, len(chars)])
		append(s, chars)
	elif op[0] == '2':
		chars = s[-int(op[1]):]
		undo.append([append, chars])
		delete(s, len(chars))
	elif op[0] == '3':
		print(s[int(op[1]) - 1])
	elif op[0] == '4':
		if len(undo) > 0:
			(undoOp, arg) = undo.pop()
			undoOp(s, arg)


operations = []
s = []

class Append:

	def __init__(self, s, w):
		self.s = s
		self.w = list(w)

	def do(self):
		self.s += self.w
		operations.append(self)

	def undo(self):
		del self.s[-len(self.w):]

class Erase:

	def __init__(self, s, k):
		self.s = s
		self.k = k
		self.erased = None

	def do(self):
		x = slice(-self.k, None)
		self.erased = self.s[x]
		del self.s[x]
		operations.append(self)

	def undo(self):
		self.s += self.erased

class Get:

	def __init__(self, s, k):
		self.s = s
		self.k = k - 1

	def do(self):
		print(self.s[self.k])

	def undo(self):
		pass

class Undo:

	def __init__(self):
		self.target = None

	def do(self):
		self.target = operations.pop()
		self.target.undo()

	def undo(self):
		pass
Q = int(input())
for _ in range(Q):
	args = input().split(' ', 1)
	type_ = args[0]
	if len(args) > 1:
		arg = args[1]
	else:
		arg = None
	if type_ == '1':
		op = Append(s, arg)
	elif type_ == '2':
		op = Erase(s, int(arg))
	elif type_ == '3':
		op = Get(s, int(arg))
	elif type_ == '4':
		op = Undo()
	else:
		raise ValueError('Invalid type: %r', type_)
	op.do()


Q = int(input())
states = ['']
for _ in range(Q):
	(op, *param) = input().split()
	state = states[-1]
	if op == '4':
		states.pop()
	elif op == '3':
		print(state[int(param[0]) - 1])
	elif op == '2':
		states.append(state[:-int(param[0])])
	elif op == '1':
		states.append(state + param[0])


(S, stack) = ([], [])
for _ in range(int(input())):
	d = [x for x in input().split()]
	d[0] = int(d[0])
	if d[0] == 1:
		S += list(d[1])
		stack.append([1, len(d[1])])
	elif d[0] == 2:
		(S, t) = (S[:-int(d[1])], S[-int(d[1]):])
		stack.append([2, t])
	elif d[0] == 3:
		print(S[int(d[1]) - 1])
	else:
		d = stack.pop()
		if d[0] == 1:
			S = S[:-d[1]]
		else:
			S += d[1]


stack = list()
S = ''
for _ in range(int(input())):
	Q = input().strip().split()
	if Q[0] == '1':
		stack.append(S)
		S += Q[1]
	elif Q[0] == '2':
		stack.append(S)
		k = int(Q[1])
		S = S[:-k]
	elif Q[0] == '3':
		index = int(Q[1]) - 1
		print(S[index])
	elif len(stack) != 0:
		S = stack.pop()


n = int(input())
s = []
results = ''

def op_append(w, results=None, fromUndo=True):
	k = len(w)
	if not fromUndo:
		s.append((op_erase, k))
	results += w
	return results

def op_erase(k, results=None, fromUndo=True):
	w = results[-k:]
	if not fromUndo:
		s.append((op_append, w))
	return results[:-k]

def op_get(k, results):
	return results[k - 1]
for i in range(n):
	x = input().split()
	if len(x) > 1:
		(c, v) = x
		if c == '1':
			results = op_append(v, results, False)
		elif c == '2':
			results = op_erase(int(v), results, False)
		elif c == '3':
			print(op_get(int(v), results))
	else:
		(f, p) = s.pop()
		results = f(p, results)


q = int(input())
stack1 = []
stack2 = []
s = ''
op = []
val = []
for i in range(q):
	m = []
	m = [x for x in input().split()]
	op.append(m[0])
	if len(m) == 2:
		val.append(m[1])
	else:
		val.append('#')
i = 0
while q:
	if op[i] == '1':
		s += val[i]
		l = len(val[i])
		stack1.append(op[i])
		stack2.append(l)
	elif op[i] == '2':
		b = int(val[i])
		last = s[-b:]
		s = s[:-b]
		stack1.append(op[i])
		stack2.append(last)
	elif op[i] == '3':
		k = int(val[i])
		print(s[k - 1])
	else:
		if stack1[-1] == '1':
			length = stack2[-1]
			s = s[:-length]
		else:
			string = stack2[-1]
			s += string
		stack1.pop()
		stack2.pop()
	q -= 1
	i += 1


stack = []
string_S = ''
QUERIES = int(input())
for i in range(QUERIES):
	get = input().split()
	if get[0] == '1':
		string_S += get[1]
		stack.append(string_S)
	elif get[0] == '2':
		string_S = string_S[:-int(get[1])]
		stack.append(string_S)
	elif get[0] == '3':
		index = int(get[1]) - 1
		print(string_S[index:index + 1])
	elif get[0] == '4' and len(stack) > 0:
		stack.pop()
		if len(stack) > 0:
			string_S = stack[-1]
		else:
			string_S = ''


def append_word(word, text):
	for c in word:
		text.append(c)

def erase_chars(num, text):
	end_idx = len(text) - int(num)
	last_chars = text[end_idx:]
	for i in range(int(num)):
		text.pop()
	return last_chars

def get(index, text):
	index = int(index)
	return text[index - 1]

def delete_word(word, text):
	for i in range(len(word)):
		text.pop()

def add_chars(chars, text):
	for c in chars:
		text.append(c)

def undo_op(text, last_op):
	op = int(last_op[0])
	if op == 1:
		delete_word(last_op[1], text)
	else:
		add_chars(last_op[2], text)

def undo(text, op_stack):
	last_op = op_stack.pop()
	undo_op(text, last_op)

def run_op(op_arr, text, op_stack):
	op = int(op_arr[0])
	if op == 1:
		append_word(op_arr[1], text)
		op_stack.append(op_arr)
	elif op == 2:
		last_chars = erase_chars(op_arr[1], text)
		op_arr.append(last_chars)
		op_stack.append(op_arr)
	elif op == 3:
		print(get(op_arr[1], text))
	else:
		undo(text, op_stack)
num_ops = int(input().strip())
text = []
op_stack = []
for i in range(num_ops):
	run_op([n for n in input().strip().split(' ')], text, op_stack)


q = int(input())
s = []
l = 0
t = ''
while q > 0:
	op = input().split()
	if op[0] == '1':
		for ch in op[1]:
			t += ch
		s.append(t)
	elif op[0] == '2':
		i = int(op[1])
		t = t[:-i]
		s.append(t)
	elif op[0] == '3':
		k = int(op[1])
		print(t[k - 1])
	else:
		if len(s) > 0:
			s.pop()
		if len(s) > 0:
			t = s[-1]
		else:
			t = ''
	q = q - 1


stack_operations = []
stack_data = []
string = ''
for _ in range(int(input())):
	data = [x for x in input().split()]
	if len(data) == 2:
		if data[0] == '1':
			string += data[1]
			stack_operations.append(1)
			stack_data.append(data[1])
		if data[0] == '2':
			k = int(data[1])
			stack_data.append(string[len(string) - k:])
			string = string[:len(string) - k]
			stack_operations.append(2)
		if data[0] == '3':
			k = int(data[1])
			print(string[k - 1])
	else:
		idx_undo = stack_operations.pop()
		data_undo = stack_data.pop()
		if idx_undo == 1:
			string = string[:len(string) - len(data_undo)]
		if idx_undo == 2:
			string = string + data_undo


class Stack:

	def __init__(self):
		self.top = -1
		self.arr = []
		self.revquery = []
		self.qtop = -1

	def push(self, x):
		self.arr.append(x)
		self.top += 1

	def pop(self):
		if self.top != -1:
			lol = self.arr.pop()
			self.top -= 1
			return lol
		else:
			return -99

	def qpush(self, q):
		self.revquery.append(q)
		self.qtop += 1

	def retElement(self, index):
		return self.arr[index]

	def qpop(self):
		rev = self.revquery.pop()
		self.qtop = self.qtop - 1
		return rev

def doQuery(strquery, flag):
	tq = int(strquery[0])
	toPush = ''
	if tq == 1:
		for i in strquery[1]:
			s.push(i)
		if flag == 0:
			revquery = '2 ' + str(len(strquery[1]))
			s.qpush(revquery)
	elif tq == 2:
		toPush = ''
		poda = ''
		for i in range(int(strquery[1])):
			toPush = toPush + s.pop()
		if flag == 0:
			poda = toPush[::-1]
			revquery = '1 ' + poda
			s.qpush(revquery)
	elif tq == 3:
		index = int(strquery[1]) - 1
		print(s.retElement(index))
	elif tq == 4:
		revQuery = s.qpop()
		doQuery(revQuery.strip().split(' '), 1)
n = int(input())
s = Stack()
for _ in range(n):
	strquery = input().strip().split(' ')
	doQuery(strquery, 0)


import queue
N = int(input())
stack = queue.LifoQueue()
s = ''
for _ in range(N):
	args = input().split()
	if args[0] == '1':
		stack.put([1, args[1], -1])
		s += args[1]
	elif args[0] == '2':
		t = int(args[1])
		stack.put([2, s[len(s) - t:len(s)], t])
		s = s[0:len(s) - t]
	elif args[0] == '3':
		print(s[int(args[1]) - 1])
	else:
		(typ, st, position) = stack.get()
		if typ == 1:
			s = s[0:len(s) - len(st)]
		else:
			s = s + st


import sys

class Stack:

	def __init__(self):
		self.items = []

	def isEmpty(self):
		return self.items == []

	def push(self, element):
		self.items.append(element)

	def pop(self):
		return self.items.pop()

	def peek(self):
		return self.items[len(self.items) - 1]

	def size(self):
		return len(self.items)

	def getElement(self, i):
		return self.items[i - 1]
n = int(input().strip())
opstack = Stack()
istack = Stack()
dstack = Stack()
oper = None
for i in range(n):
	inp = [temp for temp in input().strip().split(' ')]
	if int(inp[0]) == 1:
		opstack.push(str(len(inp[1])) + ' i')
		for ch in inp[1]:
			istack.push(ch)
	elif int(inp[0]) == 2:
		opstack.push(inp[1] + ' d')
		for i in range(int(inp[1])):
			if not istack.isEmpty():
				dstack.push(istack.pop())
	elif int(inp[0]) == 3:
		if not istack.isEmpty():
			print(istack.getElement(int(inp[1])))
	elif int(inp[0]) == 4:
		if not opstack.isEmpty():
			oper = opstack.pop().split(' ')
			if oper[1] == 'd':
				for j in range(int(oper[0])):
					if not dstack.isEmpty():
						istack.push(dstack.pop())
			elif oper[1] == 'i':
				for j in range(int(oper[0])):
					if not istack.isEmpty():
						istack.pop()


so_many_ops = int(input())
undo_stack = []
S = ''
for op in range(so_many_ops):
	operation = input().split()
	if operation[0] == '1':
		undo_stack.append(S)
		S += operation[1]
	if operation[0] == '2':
		undo_stack.append(S)
		k = int(operation[1])
		S = S[0:-k]
	if operation[0] == '3':
		k = int(operation[1])
		print(S[k - 1])
	if operation[0] == '4':
		S = undo_stack.pop()


Q = int(input())
S = ''
S_backup = []
for _ in range(Q):
	op = tuple(input().split())
	if op[0] == '1':
		S_backup.append(S)
		S = S + op[1]
	elif op[0] == '2':
		S_backup.append(S)
		S = S[:-int(op[1])]
	elif op[0] == '3':
		print(S[int(op[1]) - 1])
	elif op[0] == '4':
		S = S_backup.pop()


t = int(input())
stack = []
S = ''
for _ in range(t):
	line = input()
	if ' ' in line:
		(cmd, operand) = line.split(' ')
		if cmd is '1':
			stack.append((1, S))
			S += operand
		elif cmd is '2':
			k = int(operand)
			stack.append((2, S))
			S = S[:-k]
		elif cmd is '3':
			k = int(operand)
			print(S[k - 1])
	else:
		cmd = int(line)
		if len(stack) > 0:
			tup = stack.pop()
			S = tup[1]


def main():
	numOperations = int(input())
	operations = []
	appendedStrings = []
	erasedStrings = []
	curString = ''
	for i in range(0, numOperations):
		inStr = input()
		if inStr == '4':
			operation = inStr
		else:
			(operation, value) = inStr.split()
		if operation == '1':
			operations.append(operation)
			curString += value
			appendedStrings.append(value)
		elif operation == '2':
			operations.append(operation)
			erasedStrings.append(curString[len(curString) - int(value):])
			curString = curString[:len(curString) - int(value)]
		elif operation == '3':
			print(curString[int(value) - 1])
		elif operation == '4':
			lastOperation = operations.pop()
			if lastOperation == '1':
				lengthOfStringAppended = len(appendedStrings.pop())
				curString = curString[:len(curString) - lengthOfStringAppended]
			elif lastOperation == '2':
				erasedString = erasedStrings.pop()
				curString += erasedString
main()


no_ops = int(input())
ops = []
s = []
for i in range(no_ops):
	one_op = input().split(' ')
	ops.append(one_op)
from copy import copy
history = []
for op in ops:
	if op[0] == '1':
		to_append = op[1]
		history.append(copy(s))
		s.extend(to_append)
	elif op[0] == '2':
		k = int(op[1])
		history.append(copy(s))
		del s[-k:]
	elif op[0] == '3':
		k = int(op[1])
		print(s[k - 1])
	elif op[0] == '4':
		s = history.pop()


import collections

def undo_append(buffer, length):

	def operation():
		return buffer[:-length]
	return operation

def undo_remove(buffer, substr):

	def operation():
		return buffer + substr
	return operation
op_count = int(input().strip())
undo = collections.deque()
buffer = ''
for _ in range(op_count):
	op = input().strip()
	if op.startswith('1'):
		param = op.split(' ')[-1]
		buffer += param
		length = len(param)
		undo.append(undo_append(buffer, length))
	elif op.startswith('2'):
		param = int(op.split(' ')[-1])
		(buffer, substr) = (buffer[:-param], buffer[-param:])
		undo.append(undo_remove(buffer, substr))
	elif op.startswith('3'):
		param = int(op.split(' ')[-1])
		print(buffer[param - 1])
	else:
		buffer = undo.pop()()


s = ''
st = []
for q in range(int(input())):
	inp = input().split()
	if inp[0] == '1':
		s = s + inp[1]
		st.append(inp)
	elif inp[0] == '2':
		k = int(inp[1])
		s1 = s[-k:]
		s = s[:-k]
		st.append(['2', s1])
	elif inp[0] == '3':
		print(s[int(inp[1]) - 1])
	else:
		if st[-1][0] == '1':
			s = s[:-len(st[-1][1])]
		else:
			s = s + st[-1][1]
		st.pop(-1)


from collections import deque

def perform(op, stack, s, undo=False):
	if op[0] == '1':
		w = op.split()[1]
		if not undo:
			stack.append(('2', str(len(w))))
		s += w
	elif op[0] == '2':
		k = int(op.split()[1])
		if not undo:
			stack.append(('1', s[0 - k:]))
		s = s[:0 - k]
	elif op[0] == '3':
		k = int(op.split()[1])
		print(s[k - 1])
	elif op[0] == '4':
		op = ' '.join(stack.pop())
		return perform(op, stack, s, True)
	return (stack, s)
q = int(input())
s = ''
stack = deque()
for i in range(q):
	op = input()
	(stack, s) = perform(op, stack, s)


num_queries = int(input().strip())
stack = ''
undo = []
for _ in range(num_queries):
	op = input().strip().split(' ')
	if op[0] == '1':
		stack += op[1]
		undo.append(' '.join(op))
	elif op[0] == '2':
		temp = stack[-1 * int(op[1]):]
		stack = stack[:-1 * int(op[1])]
		undo.append('2 ' + temp)
	elif op[0] == '3':
		print(stack[int(op[1]) - 1])
	elif op[0] == '4':
		temp = undo.pop().split(' ')
		if temp[0] == '1':
			stack = stack[:-1 * len(temp[1])]
		else:
			stack += temp[1]


s = ''
prev = s
undo = []
for T in range(int(input())):
	t = input()
	if t[0] == '1':
		undo.append(s)
		t = t[2:]
		s += t
	elif t[0] == '2':
		undo.append(s)
		l = int(t[2:])
		s = s[:len(s) - l]
	elif t[0] == '3':
		print(s[int(t[2:]) - 1])
	else:
		s = undo.pop()


q = int(input().strip())
stack = []
actions = []

def append(w, undo=False):
	w_len = len(w)
	for i in range(w_len):
		stack.append(w[i])
	if not undo:
		actions.append('1 ' + str(w_len))

def delete(k, undo=False):
	deleted = []
	for k_i in range(k):
		deleted.insert(0, stack.pop())
	if not undo:
		actions.append('2 ' + ''.join(deleted))

def undo():
	action = actions.pop()
	if action[0] == '1':
		k = int(action.split(' ')[1])
		delete(k, True)
	else:
		w = action.split(' ')[1]
		append(w, True)
for q_i in range(q):
	query = input().strip()
	cmd = query[0]
	if cmd == '1':
		w = query.split(' ')[1]
		append(w)
	elif cmd == '2':
		k = int(query.split(' ')[1])
		delete(k)
	elif cmd == '3':
		k = int(query.split(' ')[1])
		print(stack[k - 1])
	else:
		undo()


def solve(s, move, val):
	if move == '1':
		s = s + val
	else:
		n = 0 - int(val)
		s = s[:n]
	return s
n = int(input())
s = ['']
for _ in range(n):
	move = input().split()
	if move[0] == '4':
		s.pop()
	elif move[0] == '3':
		k = int(move[1]) - 1
		print(s[-1][k])
	else:
		s.append(solve(s[-1], move[0], move[1]))


S = ''
history = []
Q = int(input())
for ind in range(Q):
	i = input().split(' ')
	t = int(i[0])
	if t == 1:
		history.append(S)
		W = i[1]
		S += W
	elif t == 2:
		history.append(S)
		k = int(i[1])
		S = S[:-k]
	elif t == 3:
		k = int(i[1])
		print(S[k - 1])
	else:
		S = history.pop()


N = int(input().strip())
stack = []
S = ''
for i in range(N):
	if len(stack) == 0:
		S = ''
	else:
		S = stack[-1]
	line = input().strip().split()
	action = int(line[0])
	if action == 1:
		stack.append(S + line[1])
	elif action == 2:
		k = int(line[1])
		stack.append(S[:-k])
	elif action == 3:
		k = int(line[1])
		print(S[k - 1])
	elif action == 4:
		stack.pop()


stack = ['']
for query in range(int(input())):
	(qt, *args) = input().split()
	qt = int(qt)
	if qt == 4:
		del stack[-1]
	elif qt == 3:
		k = int(args[0])
		print(stack[-1][k - 1])
	elif qt == 2:
		k = int(args[0])
		stack.append(stack[-1][:-k])
	elif qt == 1:
		(w,) = args
		stack.append(stack[-1] + w)


T = int(input())
s = ''
rev = []
for t in range(T):
	os = input()
	op = int(os[0])
	if op == 1:
		v = os[2:]
		s += v
		rev.append((2, len(v)))
	elif op == 2:
		v = int(os[2:])
		vs = s[-v:]
		s = s[:-v]
		rev.append((1, vs))
	elif op == 3:
		v = int(os[2:])
		print(s[v - 1])
	elif op == 4:
		(op, v) = rev.pop()
		if op == 1:
			s += v
		else:
			s = s[:-v]


def apply(operation, string, stack=None):
	if operation[0] == '1':
		s = operation[2:]
		string += operation[2:]
		if stack is not None:
			stack.append('2 ' + str(len(s)))
		return (string, stack)
	elif operation[0] == '2':
		k = int(operation[2:])
		if stack is not None:
			stack.append('1 ' + string[-k:])
		string = string[:-k]
		return (string, stack)
	elif operation[0] == '3':
		index = int(operation[2:]) - 1
		if index < len(string):
			print(string[index])
		else:
			print()
		return (string, stack)
	elif operation[0] == '4':
		if stack:
			(s, _) = apply(stack.pop(), string)
		else:
			s = string
		return (s, stack)
string = ''
stack = []
for _ in range(int(input())):
	(string, stack) = apply(input(), string, stack)


def printk(arr, k):
	print(arr[k - 1])

def delk(arr, k):
	supk = len(arr) - k
	arr = arr[0:supk]
	return arr

def app(arr, str):
	arr = arr + str
	return arr
nn = int(input())
point = []
arr = ''
point.append(arr)
ind = 0
for i in range(nn):
	task = [x for x in input().split()]
	if task[0] == '1':
		arr = app(arr, str(task[1]))
		ind += 1
	elif task[0] == '3':
		printk(arr, int(task[1]))
	elif task[0] == '2':
		arr = delk(arr, int(task[1]))
		ind += 1
	elif task[0] == '4':
		arr = point[ind - 1]
		ind = ind - 1
	if len(point) - 1 >= ind:
		point[ind] = arr
	else:
		point.append(arr)


editor = []
order_stack = []

def editor_append(word, save_query=True):
	for i in word:
		editor.append(i)
	if save_query:
		order_stack.append(['2', len(word)])

def editor_print(number, save_query=True):
	print(editor[number - 1])

def editor_delete(number, save_query=True):
	delete_word = ''
	for i in range(number):
		delete_word += editor.pop()
	if save_query:
		reverse_word = ''
		for i in reversed(delete_word):
			reverse_word += i
		order_stack.append(['1', reverse_word])

def editor_undo():
	query = order_stack.pop()
	handle_query(query, False)

def handle_query(query, save_query=True):
	command = query[0]
	if command == '1':
		editor_append(query[1], save_query)
	elif command == '2':
		editor_delete(int(query[1]), save_query)
	elif command == '3':
		editor_print(int(query[1]), save_query)
	elif command == '4':
		editor_undo()
n = int(input())
for _ in range(n):
	query = input().split()
	handle_query(query)


import sys

class Stack:

	def __init__(self):
		self.operation = []

	def push(self, W):
		self.operation.append(W)

	def pop(self):
		return self.operation.pop()

	def empty(self):
		if len(self.operation) is 0:
			return 1
		return 0
n = int(input())
s = ''
stk = Stack()
for i in range(0, n):
	q = input().strip()
	if q[0] is '1':
		(qry, w) = q.split(' ')
		s = s + w.strip()
		stk.push('1 ' + str(len(w.strip())))
	elif q[0] is '2':
		if len(s) is not 0:
			(qry, w) = q.split(' ')
			if len(s) >= int(w):
				rmv = s
				rmv = rmv[len(s) - int(w):]
				s = s[:-int(w)]
				stk.push('2 ' + rmv)
	elif q[0] is '3':
		(qry, w) = q.split(' ')
		if len(s) >= int(w):
			print(s[int(w) - 1])
	elif stk.empty() == 0:
		qry = stk.pop()
		if qry[0] is '1':
			(q, w) = qry.split(' ')
			s = s[:-int(w)]
		else:
			(q, w) = qry.split(' ')
			s = s + w


S = ''
updation = []
for i in range(int(input())):
	list1 = [data for data in input().strip().split()]
	if int(list1[0]) == 1:
		S += list1[1]
		updation.append(S)
	if int(list1[0]) == 2:
		S = S[:-int(list1[1])]
		updation.append(S)
	if int(list1[0]) == 3:
		print(S[int(list1[1]) - 1:int(list1[1])])
	if int(list1[0]) == 4:
		updation.pop()
		if updation != []:
			S = updation[-1]
		else:
			S = ''


t = int(input())
stack = []
string = ''
stack.append(string)
current_string = stack[-1]
for i in range(t):
	x = input().strip().split()
	if len(x) == 2:
		[arg1, arg2] = [int(x[0]), x[1]]
		if arg1 == 1:
			current_string += arg2
			stack.append(current_string)
		elif arg1 == 2:
			arg2 = int(arg2)
			current_string = current_string[:-arg2]
			stack.append(current_string)
		elif arg1 == 3:
			arg2 = int(arg2)
			print(current_string[arg2 - 1])
		current_string = stack[-1]
	elif len(x) == 1:
		stack.pop(-1)
		current_string = stack[-1]


buffer = []
command_buffer = []
delete_buffer = []

def edit_text(operation, arg=None):
	if operation == 1 and arg:
		buffer.extend(list(arg))
	elif operation == 2 and int(arg):
		for i in range(int(arg)):
			delete_buffer.append(buffer.pop())
	elif operation == 3 and int(arg):
		print(buffer[int(arg) - 1])
	elif operation == 4:
		popping_commands = True
		while True:
			last_command = command_buffer.pop()
			lc = int(last_command[0])
			if lc == 1:
				for i in range(len(last_command[1])):
					buffer.pop()
				break
			elif lc == 2:
				for i in range(int(last_command[1])):
					buffer.append(delete_buffer.pop())
				break
num_operations = int(input())
for x in range(num_operations):
	operation = input().split(' ')
	command_buffer.append(operation)
	if len(operation) > 1:
		edit_text(int(operation[0]), operation[1])
	else:
		edit_text(int(operation[0]))


class Stack:

	def __init__(self):
		self.lst = []

	def push(self, item):
		self.lst.append(item)

	def pop(self):
		return self.lst.pop()

	def peek(self):
		return self.lst[len(self.lst) - 1]

	def isEmpty(self):
		return len(self.lst) == 0

	def size(self):
		return len(self.lst)
num_of_ops = int(input())
stk = Stack()
str = ''
stk.push(str)
for i in range(num_of_ops):
	cmd = input().split()
	cmd[0] = int(cmd[0])
	if cmd[0] == 1:
		str += cmd[1]
		stk.push(str)
	elif cmd[0] == 2:
		str = str[:len(str) - int(cmd[1])]
		stk.push(str)
	elif cmd[0] == 3:
		print(str[int(cmd[1]) - 1])
	elif cmd[0] == 4:
		stk.pop()
		str = stk.peek()


buffer = []
command_buffer = []
delete_buffer = []

def edit_text(operation, arg=None):
	if operation == 1 and arg:
		buffer.extend(list(arg))
	elif operation == 2 and int(arg):
		for i in range(int(arg)):
			delete_buffer.append(buffer.pop())
	elif operation == 3 and int(arg):
		print(buffer[int(arg) - 1])
	elif operation == 4:
		popping_commands = True
		while True:
			last_command = command_buffer.pop()
			lc = int(last_command[0])
			if lc == 1:
				for i in range(len(last_command[1])):
					buffer.pop()
				break
			elif lc == 2:
				for i in range(int(last_command[1])):
					buffer.append(delete_buffer.pop())
				break
num_operations = int(input())
for x in range(num_operations):
	operation = input().split(' ')
	command_buffer.append(operation)
	if len(operation) > 1:
		edit_text(int(operation[0]), operation[1])
	else:
		edit_text(int(operation[0]))


n = int(input().strip())
undo_list = list()
s = ''
i = 0
while i < n:
	op_list = input().strip().split()
	op = int(op_list[0])
	if op == 1:
		undo_list.append((1, len(op_list[1])))
		s = ''.join([s, op_list[1]])
	elif op == 2:
		undo_list.append((2, s[len(s) - int(op_list[1]):]))
		s = s[:-int(op_list[1])]
	elif op == 3:
		print(s[int(op_list[1]) - 1])
	elif op == 4:
		(undo_op, data) = undo_list.pop()
		if undo_op == 1:
			s = s[:-data]
		elif undo_op == 2:
			s = ''.join([s, data])
	i += 1


class AppendCmd:

	def execute(self, stack, value):
		self.length = len(value)
		stack.extend(value)

	def revert(self, stack):
		for _ in range(self.length):
			stack.pop()

class EraseCmd:

	def execute(self, stack, value):
		self.text = stack[-value:]
		for _ in range(value):
			stack.pop()

	def revert(self, stack):
		stack.extend(self.text)

class CustomStack:

	def __init__(self):
		self.stack = []
		self.cmds = []

	def push(self, value):
		cmd = AppendCmd()
		cmd.execute(self.stack, value)
		self.cmds.append(cmd)

	def pop(self, value):
		cmd = EraseCmd()
		cmd.execute(self.stack, value)
		self.cmds.append(cmd)

	def get(self, value):
		print(self.stack[value])

	def revert(self):
		cmd = self.cmds.pop()
		cmd.revert(self.stack)

def main():
	cs = CustomStack()
	N = int(input())
	for _ in range(N):
		unknown = input()
		command = unknown[0]
		if command == '1':
			(cmd, value) = unknown.split()
			cs.push(list(value))
		elif command == '2':
			(cmd, value) = map(int, unknown.split())
			cs.pop(value)
		elif command == '3':
			(cmd, value) = map(int, unknown.split())
			cs.get(value - 1)
		else:
			cs.revert()
main()


buffer = []
command_buffer = []
delete_buffer = []

def process_text(op, arg=None):
	if op == 1 and arg:
		buffer.extend(list(arg))
	elif op == 2 and int(arg):
		for i in range(int(arg)):
			delete_buffer.append(buffer.pop())
	elif op == 3 and int(arg):
		print(buffer[int(arg) - 1])
	elif op == 4:
		popper = True
		while True:
			last_comm = command_buffer.pop()
			lc = int(last_comm[0])
			if lc == 1:
				for i in range(len(last_comm[1])):
					buffer.pop()
				break
			elif lc == 2:
				for i in range(int(last_comm[1])):
					buffer.append(delete_buffer.pop())
				break
noc = int(input())
for x in range(noc):
	ops = input().split(' ')
	command_buffer.append(ops)
	if len(ops) > 1:
		process_text(int(ops[0]), ops[1])
	else:
		process_text(int(ops[0]))


buffer = []
command_buffer = []
delete_buffer = []

def edit_text(operation, arg=None):
	if operation == 1 and arg:
		buffer.extend(list(arg))
	elif operation == 2 and int(arg):
		for i in range(int(arg)):
			delete_buffer.append(buffer.pop())
	elif operation == 3 and int(arg):
		print(buffer[int(arg) - 1])
	elif operation == 4:
		popping_commands = True
		while True:
			last_command = command_buffer.pop()
			lc = int(last_command[0])
			if lc == 1:
				for i in range(len(last_command[1])):
					buffer.pop()
				break
			elif lc == 2:
				for i in range(int(last_command[1])):
					buffer.append(delete_buffer.pop())
				break
num_operations = int(input())
for x in range(num_operations):
	operation = input().split(' ')
	command_buffer.append(operation)
	if len(operation) > 1:
		edit_text(int(operation[0]), operation[1])
	else:
		edit_text(int(operation[0]))


class AppendCommand:

	def do(self, s, content):
		content += list(s)
		self.s = s

	def undo(self, content):
		del content[len(content) - len(self.s):]

class DeleteCommand:

	def do(self, n, content):
		self.s = content[len(content) - n:]
		del content[len(content) - n:]

	def undo(self, content):
		content += list(self.s)
cases = int(input())
content = []
commands = []
for c in range(cases):
	inx = input().strip().split(' ')
	op = int(inx[0])
	if op is 1:
		val = inx[1]
		cmd = AppendCommand()
		cmd.do(val, content)
		commands.append(cmd)
	elif op is 2:
		val = int(inx[1])
		cmd = DeleteCommand()
		cmd.do(val, content)
		commands.append(cmd)
	elif op is 3:
		val = int(inx[1])
		print(content[val - 1])
	elif op is 4:
		cmd = commands.pop()
		cmd.undo(content)


Q = int(input())
current_ptr = -1
dic_undo = list()
string = str()
for i in range(Q):
	operation = input()
	spaces = 0
	for j in range(len(operation)):
		if operation[j] == ' ':
			spaces += 1
	if spaces == 0:
		operation = int(operation)
	else:
		(operation, value) = operation.split(' ')
		operation = int(operation)
	if operation == 1:
		string += value
		dic_undo.append('1 ' + str(current_ptr))
		current_ptr += len(value)
	elif operation == 2:
		temp = current_ptr
		current_ptr -= int(value)
		dic_undo.append('2 ' + string[current_ptr + 1:temp + 1])
		string = string[0:current_ptr + 1]
	elif operation == 3:
		print(string[int(value) - 1])
	else:
		(temp_operation, temp_value) = dic_undo.pop().split(' ')
		if int(temp_operation) == 1:
			current_ptr = int(temp_value)
			string = string[0:current_ptr + 1]
		else:
			string += temp_value
			current_ptr += len(temp_value)


def appendInstr(stack, s):
	size = len(stack)
	top = stack[size - 1]
	newStr = top + s
	stack.append(newStr)

def delInstr(stack, k):
	size = len(stack)
	top = stack[size - 1]
	newStr = top[:len(top) - k]
	stack.append(newStr)

def printInstr(stack, num):
	size = len(stack)
	top = stack[size - 1]
	try:
		print(top[num - 1])
	except IndexError:
		print('Index Error in printInstr')

def undoInstr(stack):
	stack.pop()

def main():
	stack = ['']
	Q = int(input().strip())
	for i in range(Q):
		instr = input().strip().split(' ')
		type = int(instr[0])
		if type == 1:
			inp = instr[1]
			appendInstr(stack, inp)
		elif type == 2:
			inp = int(instr[1])
			delInstr(stack, inp)
		elif type == 3:
			inp = int(instr[1])
			printInstr(stack, inp)
		else:
			undoInstr(stack)
main()


buffer = []
command_buffer = []
delete_buffer = []

def edit_text(operation, arg=None):
	if operation == 1 and arg:
		buffer.extend(list(arg))
	elif operation == 2 and int(arg):
		for i in range(int(arg)):
			delete_buffer.append(buffer.pop())
	elif operation == 3 and int(arg):
		print(buffer[int(arg) - 1])
	elif operation == 4:
		popping_commands = True
		while True:
			last_command = command_buffer.pop()
			lc = int(last_command[0])
			if lc == 1:
				for i in range(len(last_command[1])):
					buffer.pop()
				break
			elif lc == 2:
				for i in range(int(last_command[1])):
					buffer.append(delete_buffer.pop())
				break
num_operations = int(input())
for x in range(num_operations):
	operation = input().split(' ')
	command_buffer.append(operation)
	if len(operation) > 1:
		edit_text(int(operation[0]), operation[1])
	else:
		edit_text(int(operation[0]))


prev = ['']
a = ''
for i in range(int(input())):
	x = [x for x in input().split()]
	if int(x[0]) == 1:
		prev.append(a)
		a = a + x[1]
	elif int(x[0]) == 2:
		prev.append(a)
		a = a[:-int(x[1])]
	elif int(x[0]) == 3:
		print(a[int(x[1]) - 1])
	elif int(x[0]) == 4:
		a = prev.pop()


buffer = []
command_buffer = []
delete_buffer = []

def edit_text(operation, arg=None):
	if operation == 1 and arg:
		buffer.extend(list(arg))
	elif operation == 2 and int(arg):
		for _ in range(int(arg)):
			delete_buffer.append(buffer.pop())
	elif operation == 3 and int(arg):
		print(buffer[int(arg) - 1])
	elif operation == 4:
		while True:
			last_command = command_buffer.pop()
			lc = int(last_command[0])
			if lc == 1:
				for _ in range(len(last_command[1])):
					buffer.pop()
				break
			elif lc == 2:
				for _ in range(int(last_command[1])):
					buffer.append(delete_buffer.pop())
				break
for _ in range(int(input())):
	operation = input().split()
	command_buffer.append(operation)
	if len(operation) > 1:
		edit_text(int(operation[0]), operation[1])
	else:
		edit_text(int(operation[0]))


from collections import deque

class EditableString:

	def __init__(self):
		(self.s, self.ops) = ([], deque())

	def append(self, w):
		arg = list(w)
		self.s.extend(arg)
		self.ops.append(('a', len(arg)))

	def delete(self, k):
		arg = self.s[len(self.s) - k:]
		del self.s[len(self.s) - k:]
		self.ops.append(('d', arg))

	def get(self, k):
		return self.s[k - 1]

	def undo(self):
		(operation, arg) = self.ops.pop()
		if operation == 'a':
			del self.s[len(self.s) - arg:]
		elif operation == 'd':
			self.s.extend(arg)
(e, n) = (EditableString(), int(input()))
for _ in range(n):
	s = input().split()
	if len(s) == 1:
		k = int(s[0])
		e.undo()
	else:
		(op, arg) = s
		if op == '1':
			e.append(arg)
		elif op == '2':
			e.delete(int(arg))
		elif op == '3':
			print(e.get(int(arg)))


t = int(input())
string = ''
ops = []
for t_ in range(t):
	inp = input().split()
	if inp[0] != '4':
		b = inp[1]
	a = inp[0]
	if a == '1':
		string += b
		ops.append(('1', b))
	elif a == '2':
		ops.append(('2', string[len(string) - int(b):]))
		string = string[:len(string) - int(b)]
	elif a == '3':
		print(string[int(b) - 1])
	else:
		op = ops[-1]
		del ops[-1]
		if op[0] == '1':
			string = string[:len(string) - len(op[1])]
		else:
			string += op[1]


states = []
Q = int(input())
for _ in range(Q):
	query = input().split()
	operation = int(query[0])
	last_state = states[-1] if states else ''
	if operation == 1:
		states.append(last_state + query[1])
	elif operation == 2:
		states.append(last_state[:-int(query[1])])
	elif operation == 3:
		print(last_state[int(query[1]) - 1])
	elif operation == 4:
		states.pop()


query = input()
stack = []
copy_stack = []
for i in range(0, int(query)):
	in_list = list(input().split(' '))
	if in_list[0] == '1':
		copy_stack.append(list(stack))
		for item in list(in_list[1]):
			stack.append(item)
	elif in_list[0] == '2':
		k = int(in_list[1])
		copy_stack.append(list(stack))
		for i in range(len(stack) - 1, len(stack) - k - 1, -1):
			stack.pop(i)
	elif in_list[0] == '3':
		print(stack[int(in_list[1]) - 1])
	elif in_list[0] == '4':
		stack = copy_stack.pop()


(stack, string) = ([], '')
for _ in range(int(input())):
	t = input().split()
	if t[0] == '4':
		string = stack.pop()
	elif t[0] == '3':
		print(string[int(t[1]) - 1])
	else:
		stack.append(string)
		if t[0] == '1':
			string += t[1]
		else:
			string = string[:-int(t[1])]


s = ''
length = 0
qhist = []
qnum = int(input())
for _ in range(qnum):
	q = input().split(' ')
	if q[0] == '1':
		s += q[1]
		qhist.append((1, str(length)))
		length += len(q[1])
	elif q[0] == '2':
		k = int(q[1])
		(s, deleted) = (s[:-k], s[-k:])
		length -= k
		qhist.append((2, deleted))
	elif q[0] == '3':
		print(s[int(q[1]) - 1])
	else:
		if len(qhist) == 0:
			continue
		(undo, info) = qhist.pop()
		if undo == 1:
			(s, length) = (s[:int(info)], int(info))
		else:
			s += info
			length += len(info)


(s, l) = ('', [])
for i in range(int(input())):
	t = input().split()
	if t[0] == '1':
		s += t[1]
		l.append(-len(t[1]))
	elif t[0] == '2':
		t[1] = -int(t[1])
		l.append(s[t[1]:])
		s = s[:t[1]]
	elif t[0] == '3':
		print(s[int(t[1]) - 1])
	else:
		t = l.pop()
		if type(t) is int:
			s = s[:t]
		else:
			s += t


n = int(input())
stack = []
string = ''
for i in range(0, n):
	operation = input().split()
	if operation[0] == '1':
		stack.append(string)
		string += operation[1]
	elif operation[0] == '2':
		stack.append(string)
		string = string[:len(string) - int(operation[1])]
	elif operation[0] == '3':
		print(string[int(operation[1]) - 1])
	else:
		string = stack.pop()


t = int(input())
stack = []
string = ''
while t > 0:
	p = input().split()
	if p[0] == '1':
		stack.append(string)
		string += p[1]
	elif p[0] == '2':
		stack.append(string)
		string = string[:len(string) - int(p[1])]
	elif p[0] == '3':
		print(string[int(p[1]) - 1])
	elif p[0] == '4':
		string = stack.pop()
	t = t - 1


n = int(input())
stack = []
string = ''
for i in range(n):
	c = input().split()
	if c[0] == '1':
		stack.append(string)
		string += c[1]
	elif c[0] == '2':
		stack.append(string)
		string = string[:len(string) - int(c[1])]
	elif c[0] == '3':
		print(string[int(c[1]) - 1])
	else:
		string = stack.pop()


n = int(input())
stack = []
string = ''
for i in range(0, n):
	operation = input().split()
	if operation[0] == '1':
		stack.append(string)
		string += operation[1]
	elif operation[0] == '2':
		stack.append(string)
		string = string[:len(string) - int(operation[1])]
	elif operation[0] == '3':
		print(string[int(operation[1]) - 1])
	else:
		string = stack.pop()


def main():
	N = int(input().strip())
	undo_stack = []
	s = ''
	for i in list(range(N)):
		cmds = input().split()
		if int(cmds[0]) == 1:
			undo_stack.append(s)
			s += cmds[1]
		elif int(cmds[0]) == 2:
			undo_stack.append(s)
			idx = int(cmds[1].strip())
			s = s[:-idx]
		elif int(cmds[0]) == 3:
			idx = int(cmds[1].strip())
			print(s[idx - 1])
		else:
			s = undo_stack.pop()
main()


stack = []
curr = ''
N = int(input())
while N > 0:
	instr = input().strip('\n').split(' ', 1)
	op = int(instr[0])
	if op == 1:
		arg = instr[1]
		stack.append(curr)
		curr = curr + arg
	elif op == 2:
		arg = int(instr[1])
		stack.append(curr)
		curr = curr[:-arg]
	elif op == 3:
		arg = int(instr[1])
		print(curr[arg - 1])
	elif op == 4:
		curr = stack.pop()
	N -= 1


n = int(input())
stack = []
string = ''
for i in range(0, n):
	operation = input().split()
	if operation[0] == '1':
		stack.append(string)
		string += operation[1]
	elif operation[0] == '2':
		stack.append(string)
		string = string[:len(string) - int(operation[1])]
	elif operation[0] == '3':
		print(string[int(operation[1]) - 1])
	else:
		string = stack.pop()


q = int(input())
str = ''
stack = []
for i in range(0, q):
	tmp = input()
	t = int(tmp.split()[0])
	if t == 1:
		w = tmp.split()[1]
		stack.append(str)
		str = str + w
	elif t == 2:
		k = int(tmp.split()[1])
		stack.append(str)
		str = str[0:len(str) - k]
	elif t == 3:
		k = int(tmp.split()[1])
		print(str[k - 1])
	elif t == 4:
		str = stack.pop()


n = int(input())
S = ['']
while n != 0:
	n -= 1
	temp = [i for i in input().split()]
	if temp[0] == '1':
		S.append(S[-1] + temp[1])
	elif temp[0] == '2':
		k = int(temp[1])
		length = len(S[-1])
		S.append(S[-1][:length - k])
	elif temp[0] == '3':
		print(S[-1][int(temp[1]) - 1])
	else:
		S.pop()


n = int(input())
stack = []
string = ''
for i in range(0, n):
	operation = input().split()
	if operation[0] == '1':
		stack.append(string)
		string += operation[1]
	elif operation[0] == '2':
		stack.append(string)
		string = string[:len(string) - int(operation[1])]
	elif operation[0] == '3':
		print(string[int(operation[1]) - 1])
	else:
		string = stack.pop()


Q = int(input())
stack = []
s = ''
for i in range(0, Q):
	query = input()
	if query[0] == '1':
		w = query[2:]
		s += w
		stack.append(1)
		stack.append(w)
	elif query[0] == '2':
		k = int(query[2:])
		l = len(s)
		w = s[l - k:]
		s = s[:l - k]
		stack.append(2)
		stack.append(w)
	elif query[0] == '3':
		k = int(query[2:])
		print(s[k - 1])
	elif query[0] == '4':
		top = len(stack) - 1
		w = stack.pop(top)
		qt = stack.pop(top - 1)
		if qt == 1:
			l = len(s)
			k = len(w)
			s = s[:l - k]
		elif qt == 2:
			s += w


q = int(input())
S = ''
old = []
for i in range(q):
	line = input().strip().split()
	cmd = int(line[0])
	if cmd != 4:
		arg = line[1]
	if cmd == 1:
		old.append(S)
		S = S + arg
	elif cmd == 2:
		old.append(S)
		S = S[:-int(arg)]
	elif cmd == 3:
		print(S[int(arg) - 1])
	else:
		S = old.pop()


n = int(input())
stack = [[]]
state = 0
for i in range(n):
	s = input()
	x = int(s[0])
	if x == 1:
		(a, b) = [z for z in s.split()]
		stack.append(stack[state].copy())
		state = state + 1
		for i in range(len(b)):
			stack[state].append(b[i])
	elif x == 2:
		(a, b) = [int(z) for z in s.split()]
		stack.append(stack[state].copy())
		state = state + 1
		for i in range(b):
			stack[state].pop()
	elif x == 3:
		(a, b) = [int(z) for z in s.split()]
		print(stack[state][b - 1])
	elif x == 4:
		stack.pop()
		state = state - 1


q = int(input())
s = ''
sList = []
for i in range(q):
	argvs = input().split()
	if argvs[0] == '1':
		sList.append(s)
		s += argvs[1]
	elif argvs[0] == '2':
		sList.append(s)
		k = int(argvs[1])
		s = s[:len(s) - k]
	elif argvs[0] == '3':
		print(s[int(argvs[1]) - 1])
	else:
		s = sList.pop()


__author__ = 'abdujabbor'
s = ''
os = []
inputs = []
deletes = []
q = int(input())
commands = []
for x in range(q):
	values = input().split()
	command = int(values[0])
	if command == 1:
		s += values[1]
		inputs.append(values[1])
		commands.append(command)
		pass
	elif command == 2:
		deletes.append(s[len(s) - int(values[1]):])
		s = s[:len(s) - int(values[1])]
		commands.append(command)
		pass
	elif command == 3:
		print(s[int(values[1]) - 1])
	else:
		latest_command = commands.pop()
		if latest_command == 1:
			linput = inputs.pop()
			s = s[:len(s) - len(linput)]
			pass
		else:
			s = s + deletes.pop()


class String(object):

	def __init__(self):
		self.stack = ['']

	def append(self, chars):
		self.stack.append(self.stack[-1] + chars)

	def delete(self, num_chars):
		self.stack.append(self.stack[-1][:-num_chars])

	def print(self, char_num):
		print(list(self.stack[-1])[char_num - 1])

	def undo(self):
		self.stack.pop()
string = String()
num_tests = int(input().strip())
for t in range(num_tests):
	command = input().strip().split()
	if command[0] == '1':
		string.append(command[1])
	elif command[0] == '2':
		string.delete(int(command[1]))
	elif command[0] == '3':
		string.print(int(command[1]))
	elif command[0] == '4':
		string.undo()


Q = int(input())
s = ''
ops = []
for i in range(Q):
	v = input().strip().split(' ')
	if len(v) == 0:
		continue
	t = int(v[0])
	arg = None
	if t != 4:
		if len(v) < 2:
			continue
		arg = v[1]
	if t == 1:
		s += arg
		ops.append((t, arg))
	elif t == 2:
		arg = int(arg)
		ops.append((t, s[-arg:]))
		s = s[:-arg]
	elif t == 3:
		arg = int(arg) - 1
		print(s[arg])
	elif t == 4:
		(op_t, op_arg) = ops.pop()
		if op_t == 1:
			s = s[:-len(op_arg)]
		elif op_t == 2:
			s += op_arg


from collections import deque
states = deque('')
for i in range(int(input())):
	line = input().split()
	query = line[0]
	if query == '1':
		states.append((states[-1] if len(states) else '') + line[1])
	elif query == '2':
		states.append(states[-1][:-int(line[1])])
	elif query == '3':
		print(states[-1][int(line[1]) - 1])
	elif query == '4':
		states.pop()


test_cases = int(input())
s = ''
past_s = []
for test_case in range(test_cases):
	command = input().split()
	if command[0] == '1':
		past_s.append(s)
		s += command[1]
	elif command[0] == '2':
		past_s.append(s)
		s = s[:-int(command[1])]
	elif command[0] == '3':
		print(s[int(command[1]) - 1])
	elif command[0] == '4':
		s = past_s.pop()


class Stack:

	def __init__(self):
		self.data = []

	def push(self, x):
		self.data.append(x)

	def peek(self):
		return self.data[-1]

	def delete(self):
		return self.data.pop()

	def is_empty(self):
		return len(self.data) == 0

def append(stack, word):
	last_word = ''
	if not stack.is_empty():
		last_word = stack.peek()
	stack.push(last_word + word)

def delete(stack, k):
	last_word = stack.peek()
	word = last_word[:-k]
	stack.push(word)

def print_stack(stack, k):
	word = stack.peek()
	print(word[k - 1])

def undo(stack):
	stack.delete()
n = int(input())
stack = Stack()
for _ in range(n):
	query = input().strip().split()
	type = int(query[0])
	if type == 1:
		word = query[1]
		append(stack, word)
	elif type == 2:
		k = int(query[1])
		delete(stack, k)
	elif type == 3:
		k = int(query[1])
		print_stack(stack, k)
	else:
		undo(stack)