eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

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

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

Ліміт часу 2 секунди
Ліміт використання пам'яті 256 MiB

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

Вхідні дані

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

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

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

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

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

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

Вихідні дані

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

Приклад

Вхідні дані #1
9
pushfront 1 71819
pushback 2 71820
pushback 1 1
popfront 1
popfront 1
pushfront 2 10
pushback 2 11
popback 2
popback 2
Вихідні дані #1
71819
1
11
71820