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

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

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

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

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

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

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

Примеры