ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Разделы > 115. Задачи на структуры данных > задача:


Макс и вставка букв

Задачи раздела

• Макс и вставка букв
• Макс и начисление зарплаты

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/2000/2000/2000 мс. Лимит памяти 65536/65536/65536/65536 Кб.

Макс и вставка букв
Макс и вставка букв
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

У Макса есть строка, которая изначально пуста. Макс собирается последовательно добавить в определённые места этой строки несколько наборов одинаковых букв.

Более формально, Макс может выполнять два вида действий:

  • $$$1$$$ $$$P$$$ $$$K$$$ $$$C$$$ — вставить $$$K$$$ букв $$$C$$$ перед $$$P$$$-й буквой строки (если $$$P$$$ равно длине строки, то вставка производится в конец);
  • $$$2$$$ $$$Q$$$ — определить, какая буква находится в строке на позиции $$$Q$$$.

Если строка имеет длину $$$W$$$, то буквы в ней нумеруются слева направо числами от 0 до $$$(W - 1)$$$.

Помогите Максу проверить правильность выполнения всех операций.

Входные данные

Первая строка содержит целое число $$$N$$$ ($$$2 \le N \le 10^5$$$) — количество запросов.

Следующие $$$N$$$ строк описывают запросы. Каждая из них содержит целое число $$$T_i$$$ ($$$T_i \in \{1, 2\}$$$) — тип запроса.

Если $$$T_i = 1$$$, то далее следуют целые числа $$$P_i$$$, $$$K_i$$$ ($$$0 \le P_i$$$, $$$0 \le K_i \le 10^5$$$) и символ $$$C_i$$$ ($$$C_i \in \{\texttt{A}, ..., \texttt{Z}\}$$$) — соответственно позиция вставки, количество вставляемых букв и вид букв.

Если $$$T_i = 2$$$, то далее следует целое число $$$Q_i$$$ ($$$0 \le Q_i$$$) — позиция буквы, которую требуется вывести.

Все позиции $$$P_i$$$ и $$$Q_i$$$ в запросах корректны (не выходят за пределы строки).

Выходные данные

Для каждого запроса типа 2 выведите в отдельной строке один символ — букву, находящуюся в строке на соответствующей позиции.

Примеры

Входные данные
10
1 0 3 A
2 0
2 1
2 2
1 1 2 B
2 0
2 1
2 2
2 3
2 4
Выходные данные
A
A
A
A
B
B
A
A
Входные данные
10
1 0 4 X
2 2
1 2 2 N
2 4
1 6 5 T
2 7
1 3 4 Q
2 5
1 1 7 D
2 8
Выходные данные
X
X
T
Q
X

Для отправки решений необходимо выполнить вход.

www.contester.ru