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

Входные данные

Первая строка содержит общее количество команд 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 выведите удаляемое число. Гарантируется, что перед выполнением команды удаления соответствующий дек не пуст.