eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Персистентная очередь

Персистентная очередь

Лимит времени 2 секунды
Лимит использования памяти 64 MiB

Реализуйте персистентную очередь.

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

Первая строка содержит количество действий n (1n200000). В строке номер i + 1 содержится описание действия i:

  • 1 t m - добавить в конец очереди номер t (0t < i) число m;

  • -1 t - удалить из очереди номер t (0t < i) первый элемент.

В результате действия i, описанного в строке i + 1 создаётся очередь номер i. Изначально имеется пустая очередь с номером ноль.

Все входные числа целые и помещаются в 32-битовый знаковый тип.

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

Для каждой операции удаления выведите удалённый элемент в отдельной строке.

Пример

Входные данные #1
10
1 0 1
1 1 2
1 2 3
1 2 4
-1 3
-1 5
-1 6
-1 4
-1 8
-1 9
Выходные данные #1
1
2
3
1
2
4