Deques on 6 Megabytes

Input

The first line contains the total number of commands $n$ (0 \leq n \leq 150{,}000). Each of the next $n$ lines contains a command description:

• pushfront A B — insert the number $B$ at the front of deque $A$;

• pushback A B — insert the number $B$ at the back of deque $A$;

• popfront A — remove the first element from deque $A$;

• popback A — remove the last element from deque $A$.

In each command, $A$ and $B$ are integers from $1$ to $150,000$ inclusive.

Output

For each popfront or popback command, print the removed number. It is guaranteed that before every remove operation the corresponding deque is not empty.

Examples