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

Вхідні дані

Перший рядок містить загальну кількість команд $n$ (0 \leq n \leq 150{,}000). Кожен з наступних $n$ рядків містить опис команди:

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

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

• popfront A — видалити перший елемент з дека $A$;

• popback A — видалити останній елемент з дека $A$.

У кожній команді $A$ і $B$ — цілі числа від $1$ до $150,000$ включно.

Вихідні дані

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

Приклади