Book shelf#8355
Mamed arranges his books on a shelf. If the shelf is empty, he simply places a book there. If there are already books on the shelf, he places the new book either to the left or to the right of the existing books. Similarly, he removes books only from the left or right edge. Based on the given information, it is necessary to simulate Mamed's actions and print the numbers of the books he will remove.
The first line contains the number of operations n~(1 \le n \le 10^4) that Mamed performed. The following lines contain the details of the operations:
Each operation of placing a book on the shelf is described by a pair of numbers. The first number ( or ) indicates which edge the book is placed on (left or right), and the second number (from to 10^4) represents the number of the book.
Operations of removing a book from the shelf are described by a single number: or , indicating which edge the book is removed from (left or right).
For each operation of removing a book from the shelf, print the number of the book being removed.
Example 1