|
Лимит времени 1000/1000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Problem Description
Yesterday John laid out his books on the shelf. If the shelf is empty he simply put the book. If it's not empty then he put the book from the left or right side of them. When he wanted to pick up the book he took it from left or right edge only.
Input
The first line contains N (0 <N <10001) - the number of operations that are performed by John. Next N lines contain information about the operations. Each operation of putting the book on the shelf is described by two numbers. The first of them (1 or 2) indicates the side on the shelf (left or right), the second integer (from 0 to 10000) is the identifier of the book. Each operation of picking up the book is described with a single number, 3 if he picks up the book from the left, and 4 if he picks from the right.
Output
For each operation of picking up the book write in output its identifier.
Example
| input |
output |
5
1 1
2 2
1 3
3
4 |
3
2 |
Для отправки решений необходимо выполнить вход.
|