Deque of infinite size

Implement the "deque" data structure. Write a program that describes the deque and simulates its operations. You must implement all methods given below. The program reads the sequence of commands and executes the corresponding operation. After executing each command the program must print one line. The possible commands for the program are:

push_front

Add (put) into the front of the deque the new element. The program must print ok.

push_back

Add (put) into the end of the deque the new element. The program must printok.

pop_front

Pop the first element from the deque. The program must print its value.

pop_back

Pop the last element from the deque. The program must print its value.

front

Find the value of the first element (not deleting it). The program must print its value.

back

Find the value of the last element (not deleting it).The program must print its value

size

Print the number of elements in the deque.

clear

Clear the deque (delete all its elements) and print ok.

exit

The program must print bye and terminate.

The size of the deque is limited only by the available memory. Before the execution of the operations pop_front, pop_back, front, back the program should check first whether the deque contains at least one element. When we have the input operation pop_front, pop_back, front, back but the deque is empty, the program must print the line error instead of numeric value.

Input

Given in the problem statement. Look at sample input.

Output

Given in the problem statement.Look at sample output.