Write a program that operates with a big number of deques. Deque is a "queue with two ends".
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.
For each command popfront or popback print the deleted number. It is guaranteed that before each delete operation the corresponding deque is not empty.