e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
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 (0n150000) 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.

Time limit 2 seconds
Memory limit 256 MiB
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