Реалізуйте структуру даних "дек". Напишіть програму, яка містить опис дека і моделює роботу дека, реалізувавши усі вказані тут методи. Програма зчитує послідовність команд і у залежності від команди виконує ту чи іншу операцію. Після виконання кожної команди програма повинна вивести один рядок. Можливі команди для програми:

push_front

Додати (покласти) у початок дека новий елемент. Програма повинна вивести ok.

push_back

Додати (покласти) у кінець дека новий елемент. Програма повинна вивести ok.

pop_front

Дістати з дека перший елемент. Програма повинна вивести його значення.

pop_back

Дістати з дека останній елемент. Програма повинна вивести його значення.

front

Взнати значення першого елементу (не видаляючи його). Програма повинна вивести його значення.

back

Взнати значення останнього клемента (не видаляючи його). Програма повинна вивести його значення.

size

Вивести кількість елементів у декі.

clear

Очистити дек (видалити з нього усі елементи) і вивести ok.

exit

Програма повинна вивести bye і завершити роботу.

Гарантується, що кількість елементів у декі у довільний момент не перевищує 100. Усі операції:

• pop_front,
• pop_back,
• front,
• back

завжди коректні.

// 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();
}

Вхідні дані

Кожний рядок містить одну команду.

Вихідні дані

Для кожної команди вивести в окремому рядку відповідний результат.