Competitions

# Data Structures contest

# Deques on 6 Megabytes

Write a program that operates with a big number of deques. Deque is a "queue with two ends".

#### Input

The first line contains the number of operations **n** (**0** ≤ **n** ≤ **150000**) to operate. Each of the next **n** lines gives the operation description:

**pushfront A B**- insert the number**B**into the front of the deque**A**;**pushback A B**- insert the number**B**into the end of the deque**A**;**popfront A**- delete the first element of the deque**A**;**popback A**- delete the last element of the deque**A**.

For each operation the parameters **A** and **B** are integers in the range from **1** to **150000** inclusive.

#### Output

For each command **popfront** or **popback** print the deleted number. It is guaranteed that before each delete operation the corresponding deque is not empty.

Input example #1

9 pushfront 1 71819 pushback 2 71820 pushback 1 1 popfront 1 popfront 1 pushfront 2 10 pushback 2 11 popback 2 popback 2

Output example #1

71819 1 11 71820