Queue 2

Interview

Time limit1sMemory limit512 MB

Summary

Implement a queue supporting push, pop, size, empty, front, and back, and run N commands, printing output for the query commands.

Level: Easy3 of 10
Topics: Queue, Implementation, Simulation, Linked list
Solved: No attempts yet

Problem

Implement a queue that stores integers, then write a program that processes the commands given as input.

There are six commands in total.

push X: Insert the integer X into the queue.
pop: Remove the integer at the front of the queue and print it. If the queue contains no integer, print -1.
size: Print the number of integers in the queue.
empty: Print 1 if the queue is empty, otherwise 0.
front: Print the integer at the front of the queue. If the queue contains no integer, print -1.
back: Print the integer at the back of the queue. If the queue contains no integer, print -1.

Input

The first line gives the number of commands N (1 ≤ N ≤ 2,000,000). The next N lines each contain one command. Every integer given is greater than or equal to 1 and less than or equal to 100,000. No command other than the ones listed above is given.

Output

For every command that produces output, print the result on its own line.

Examples1

Example 1

Input

15
push 1
push 2
front
back
size
empty
pop
pop
pop
size
empty
pop
push 3
empty
front

Expected output