Simple deque

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 print ok.

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.

It is guaranteed that the number of elements in the deque at any time does not exceed 100. All the operations:

• pop_front,

• pop_back,

• front,

• back

are usually correct.

// Java OOP
class MyDeque
{
  protected LinkedList<Integer> v;
  MyDeque(); 
  public void push_back(int x);
  public void push_front(int x);
  public int pop_back();
  public int pop_front();
  public int front();
  public int back();
  public int size();
  public void clear();
  public void exit();
}

Input

Each line contains one command.

Output

For each command, print the corresponding result on a separate line.

Examples