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.