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

Книжная полка

Книжная полка

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

Мамед раскладывает свои книги на полку. Если на полке нет ни одной книги, то он просто ставит её, если есть, то ставит либо справа, либо слева от уже расставленных книг. Забирает книги он так же, то есть снимает только с правого или левого края. По задаваемой информации требуется смоделировать действия Мамеда и вывести номера книг, которые он будет снимать.

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

В первой строке содержится число n~(1 \le n \le 10000) — количество операций, которые выполнил Мамед. Далее в n строках находится информация об операциях. Каждая операция постановки книги на полку описывается парой чисел.

Первое из них (1 или 2) показывает, книга ставится с левого края или с правого соответственно, второе целое число (от 0 до 10000) обозначает номер книги. Операции снятия книги с полки описывается одним числом — 3 или 4, с левого и правого края соответственно.

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

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

Пример

Входные данные #1
10
1 1
2 2
1 3
2 7
2 9
3
4
3
3
4
Выходные данные #1
3
9
1
2
7
Источник 2018 Азербайджан, Полуфинал Республиканской олимпиады, Апрель 8