Book shelf

Mamed puts his books on the shelf. If there are no books on the shelf, he simply puts it there. If there is, then he puts the book either to the right or to the left of the books already arranged. He removes the books the same way, that is, he removes only from the right or from the left edge. By the given information you need to simulate the Mamed's actions and print the numbers of books that he will take out.

Input

The first line contains the number $n(1\le n\le 10000)$ — the number of operations performed by Mamed. The information about operations is given in the next $n$ lines. Each operation of putting the book on the shelf is described by a pair of numbers.

The first number ($1$ or $2$) shows that the book is placed from the left or from the right edge, respectively, second number (from $0$ to $10000$) denotes the book number. The operation of removing a book from the shelf is described by one number — $3$ or $4$, from the left or from the right edge respectively.

Output

For each operation of removing the book from the shelf, print out the number of the book to be taken.

Examples