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.

Examples