Read problems statements in Mandarin Chinese . 

In this problem you will have to implement a simple editor. The editor maintains the content of a string S and have two following functions:

"+ i x": insert a string x into the current string S after the i'th character of the S (we use 1-indexing in this problem). When i equals to 0 it mean we add x at the beginning of S.

"? i len": Print the sub-string of length len starting at position i'th of S.

At the beginning, the editor holds an empty string. There will be Q queries of the two types described above.

------ Input ------ 

The first line contains the integer Q.
Each line in the next Q lines contains one query.

------ Output ------ 

For each query of the second type, print out the answer sub-string in one line.

------ Constraints ------ 

$For the first type of query: 0 ≤ i ≤ |S|$
$For the second type of query: 1 ≤ i ≤ |S| - len + 1 $

20 points

$Q ≤ 1000, |S| ≤ 1000, sum of value of all lens ≤ 1000: $

30 points

$Q ≤ 10000, |S| ≤ 10000, sum of value of all lens ≤ 10000: $

50 points

$Q ≤ 3×10^{5}, |S| ≤ 3×10^{5}, sum of value of all lens ≤ 3×10^{5}: $

------ Example ------ 

Input:
5
+ 0 ab
+ 1 c
? 1 3
+ 2 dd
? 1 5

Output:
acb
acddb

------ Explanation ------ 

$"+ 0 ab": S = "ab"$
$"+ 1 c": S = "acb"$
$"+ 2 dd": S = "acddb"$

Difficulty: VERY_HARD
Tags: String algorithms

Sorting

Range queries

Segment trees revisited

Complete search

Data structures
Skill types: Sorting

Data structures

Range queries

Complete search

Starter code:

Solutions:
Q = int(input())
this_string = ''
for i in range(Q):
	command = input().split()
	ind = int(command[1])
	if command[0] == '+':
		sub_str = command[2]
		this_string = this_string[:ind] + sub_str + this_string[ind:]
	elif command[0] == '?':
		len = int(command[2])
		solution = this_string[ind - 1:ind - 1 + len]
		print(solution)


n = int(input())
s = ''
for i in range(n):
	x = input().split()
	if x[0] == '+':
		s = s[:int(x[1])] + x[2] + s[int(x[1]):]
	else:
		print(s[int(x[1]) - 1:int(x[2]) + int(x[1]) - 1])


s = ''
for q in range(int(input())):
	dat = input().split()
	if dat[0] == '+':
		i = int(dat[1])
		s = s[0:i] + dat[2] + s[i:]
	else:
		(a, b) = (int(dat[1]) - 1, int(dat[2]))
		print(s[a:a + b])


OUTPUT = ''
for i in range(int(input())):
	INPUT = input().split()
	if INPUT[0] == '+':
		OUTPUT2 = ''
		if OUTPUT == '':
			OUTPUT2 = INPUT[2]
		else:
			SLICE_OBJECT1 = slice(int(INPUT[1]))
			SLICE_OBJECT2 = slice(int(INPUT[1]), int(len(OUTPUT)))
			OUTPUT2 = OUTPUT[SLICE_OBJECT1] + INPUT[2] + OUTPUT[SLICE_OBJECT2]
		OUTPUT = OUTPUT2
	if INPUT[0] == '?':
		SLICE_OBJECT = slice(int(INPUT[1]) - 1, int(INPUT[1]) - 1 + int(INPUT[2]))
		print(OUTPUT[SLICE_OBJECT])


n = int(input())
p = ''
for i in range(n):
	(operation, index, a) = input().split()
	index = int(index)
	if operation == '+':
		p = p[:index] + a + p[index:]
	else:
		start = index - 1
		end = start + int(a)
		print(p[start:end])


q = int(input())
s = ''
for i in range(q):
	x = input().split()
	operation = x[0]
	position = int(x[1])
	if operation == '+':
		s = s[:position] + x[2] + s[position:]
	else:
		start = position - 1
		end = start + int(x[2])
		print(s[start:end])


q = int(input())
s = ''
for _ in range(q):
	cmd = input().split()
	index = int(cmd[1])
	if cmd[0] == '+':
		s = s[:index] + cmd[2] + s[index:]
	else:
		length = int(cmd[2])
		print(s[index - 1:index + length - 1])


q = int(input())
s = ''
for i in range(q):
	x = input().split()
	if x[0] == '+':
		s = s[:int(x[1])] + x[2] + s[int(x[1]):]
	elif x[0] == '?':
		print(s[int(x[1]) - 1:int(x[2]) + int(x[1]) - 1])


n = int(input())
l = []
for i in range(n):
	z = input().split()
	l.append(z)
S = ''
for i in l:
	if i[0] == '+':
		Z = S[0:int(i[1])]
		z1 = S[int(i[1]):len(S)]
		z2 = Z + i[2] + z1
		S = z2
	elif i[0] == '?':
		z3 = S[int(i[1]) - 1:int(i[2]) + int(i[1]) - 1]
		print(z3)


p = int(input())
t = ''
for _ in range(p):
	x = input().split()
	if x[0] == '+':
		t = t[:int(x[1])] + x[2] + t[int(x[1]):]
	elif x[0] == '?':
		print(t[int(x[1]) - 1:int(x[2]) + int(x[1]) - 1])


def insert(string_s, insert_s, pos_i=0):
	return string_s[:pos_i] + insert_s + string_s[pos_i:]
q = int(input())
s = ''
for _ in range(q):
	query = input().split()
	c = query[0]
	i = int(query[1])
	if c == '+':
		sub = query[2]
		if i == 0:
			s = sub + s
		else:
			s = insert(s, sub, i)
	else:
		l = int(query[2])
		print(s[i - 1:i + l - 1])