Скоро у Димы день рождения! Большой праздник! Сережа подарит Диме свое отсутствие в комнате и не будет мешать Диме и Инне праздновать день рождения. Инна подарит Диме стек, очередь и дек.
Своим подарком Инна хочет проверить, насколько Дима хороший программист. Для этого она будет поочередно давать Диме команды. Команды бывают двух типов:
- Добавить заданное число в один из контейнеров. Причем в очередь и стек можно добавлять элементы только в конец, в дек можно добавлять элементы как в начало, так и в конец.
- Извлечь из не более чем трех различных контейнеров по числу. Все извлеченные числа сказать Инне, после чего опустошить все контейнеры. Причем в контейнере очередь можно извлекать числа только из начала, в стеке — только из конца, в деке — из начала и из конца. Нельзя извлекать числа из пустых контейнеров.
Каждый раз, когда Дима выполняет команду второго типа, Инна целует Диму некоторое число (возможно, ноль) раз. Дима знает Инну как облупленную, он уверен, что это число равно сумме извлеченных из контейнеров чисел на данной операции.
Как уже было сказано, Дима знает Инну как облупленную, ему известно, какие команды Инна будет давать Диме и в каком порядке. Помогите Диме найти стратегию, используя которую, он получит как можно больше поцелуев на свой день рождения!
Выходные данные
Каждой команде из входных данных должна соответствовать одна строка выходных данных — действие Димы.
Для команды первого типа (добавление) выведите одну из строк в соответствии с выбором Димы:
- pushStack — добавить в конец стека;
- pushQueue — добавить в конец очереди;
- pushFront — добавить в начало дека;
- pushBack — добавить в конец дека.
Для команды второго типа выведите сначала целое число k (0 ≤ k ≤ 3), обозначающее количество операций извлечения, затем выведите k слов разделенных пробелом. Слова могут быть:
- popStack — извлечь из конца стека;
- popQueue — извлечь из начала очереди;
- popFront — извлечь из начала дека;
- popBack — извлечь из конца дека.
Выведенные операции не должны извлекать чисел из пустых контейнеров. А также должны извлекать числа из разных контейнеров.
Выведенная последовательность действий должна приводить к максимальному количеству поцелуев. Если существует несколько последовательностей действий, приводящих к максимальному количеству поцелуев, разрешается вывести любую из них.