Deque

Implement a deque that stores integers, then write a program that processes the commands given on the input.

There are eight commands.

• push_front X: put the integer X at the front of the deque.
• push_back X: put the integer X at the back of the deque.
• pop_front: remove the number at the front of the deque and print it. If the deque is empty, print -1.
• pop_back: remove the number at the back of the deque and print it. If the deque is empty, print -1.
• size: print how many integers the deque holds.
• empty: print 1 if the deque is empty, and 0 if it is not.
• front: print the integer at the front of the deque. If the deque is empty, print -1.
• back: print the integer at the back of the deque. If the deque is empty, print -1.

The first line holds the number of commands $N$ ($1 \le N \le 10000$). Each of the next $N$ lines holds one command. Every integer given is at least 1 and at most 100000. No command other than the eight listed above is given.

Each time a command that has to print something is given, print its result on its own line.