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

Мамед розкладає свої книги на полицю. Якщо на полиці немає жодної книги, він просто ставить її, якщо є, то ставить або праворуч, або ліворуч від уже розставлених книг. Забирає книги він так само, тобто знімає лише з правого чи лівого краю. За інформацією, що задається, потрібно змоделювати дії Мамеда і вивести номери книг, які він зніматиме.

Вхідні дані

У першому рядку міститься число $n(1\le n\le 10000)$ — кількість операцій, які виконав Мамед. Далі в $n$ рядках знаходиться інформація про операції. Кожна операція постановки на полицю описується парою чисел.

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

Вихідні дані

Для кожної операції зняття книги з полиці вивести номер книги, що знімається.

Приклади