Deque

Interview

Time limit0.5sMemory limit256 MB

Summary

Process up to 10000 push, pop, size, empty, front and back commands on an integer deque and print each query result.

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

Problem

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.

Input

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.

Output

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

Examples4

Example 1

Input

15
push_back 1
push_front 2
front
back
size
empty
pop_front
pop_back
pop_front
size
empty
pop_back
push_front 3
empty
front

Expected output

Example 2

Input

22
front
back
pop_front
pop_back
push_front 1
front
pop_back
push_back 2
back
pop_front
push_front 10
push_front 333
front
back
pop_back
pop_back
push_back 20
push_back 1234
front
back
pop_back
pop_back

Expected output

Example 3
Input
```
1
size
```
Expected output
```
0
```

Example 4

Input

4
push_back 100000
back
front
pop_front

Expected output

100000
100000
100000