Деки на 6 мегабайтах

Напишіть програму, яка вміє оперувати з великою кількістю деків. Дек - це "черга з двома кінцями".

Вхідні дані

Перший рядок містить загальну кількість команд n (0 ≤ n ≤ 150000). Кожен з наступних n рядків містить опис команди:

• pushfront A B - вставити число B на початок деку A;

• pushback A B - вставити число B в кінець деку A;

• popfront A - видалити перший елемент деку A;

• popback A - видалити останній елемент деку A.

Для кожної команди параметри A та B - цілі числа від 1 до 150000 включно.

Вихідні дані

Для кожної команди popfront або popback виведіть число, що видаляється. Гарантується, що перед виконанням команди видалення відповідний дек не порожній.

Приклади