C. Дима и контейнеры
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Скоро у Димы день рождения! Большой праздник! Сережа подарит Диме свое отсутствие в комнате и не будет мешать Диме и Инне праздновать день рождения. Инна подарит Диме стек, очередь и дек.

Своим подарком Инна хочет проверить, насколько Дима хороший программист. Для этого она будет поочередно давать Диме команды. Команды бывают двух типов:

  1. Добавить заданное число в один из контейнеров. Причем в очередь и стек можно добавлять элементы только в конец, в дек можно добавлять элементы как в начало, так и в конец.
  2. Извлечь из не более чем трех различных контейнеров по числу. Все извлеченные числа сказать Инне, после чего опустошить все контейнеры. Причем в контейнере очередь можно извлекать числа только из начала, в стеке — только из конца, в деке — из начала и из конца. Нельзя извлекать числа из пустых контейнеров.

Каждый раз, когда Дима выполняет команду второго типа, Инна целует Диму некоторое число (возможно, ноль) раз. Дима знает Инну как облупленную, он уверен, что это число равно сумме извлеченных из контейнеров чисел на данной операции.

Как уже было сказано, Дима знает Инну как облупленную, ему известно, какие команды Инна будет давать Диме и в каком порядке. Помогите Диме найти стратегию, используя которую, он получит как можно больше поцелуев на свой день рождения!

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

Первая строка содержит целое число n (1 ≤ n ≤ 105) — количество команд Инны. Далее следует n строк, описывающих команды Инны. Каждая строка содержит целое число:

  1. Целое число a (1 ≤ a ≤ 105) означает, что Инна дает Диме команду добавить число a в один из контейнеров.
  2. Целое число 0 означает, что Инна просит Диму сделать не более трех операций извлечения из различных контейнеров.
Выходные данные

Каждой команде из входных данных должна соответствовать одна строка выходных данных — действие Димы.

Для команды первого типа (добавление) выведите одну из строк в соответствии с выбором Димы:

  • pushStack — добавить в конец стека;
  • pushQueue — добавить в конец очереди;
  • pushFront — добавить в начало дека;
  • pushBack — добавить в конец дека.

Для команды второго типа выведите сначала целое число k (0 ≤ k ≤ 3), обозначающее количество операций извлечения, затем выведите k слов разделенных пробелом. Слова могут быть:

  • popStack — извлечь из конца стека;
  • popQueue — извлечь из начала очереди;
  • popFront — извлечь из начала дека;
  • popBack — извлечь из конца дека.

Выведенные операции не должны извлекать чисел из пустых контейнеров. А также должны извлекать числа из разных контейнеров.

Выведенная последовательность действий должна приводить к максимальному количеству поцелуев. Если существует несколько последовательностей действий, приводящих к максимальному количеству поцелуев, разрешается вывести любую из них.

Примеры
Входные данные
10
0
1
0
1
2
0
1
2
3
0
Выходные данные
0
pushStack
1 popStack
pushStack
pushQueue
2 popStack popQueue
pushStack
pushQueue
pushFront
3 popStack popQueue popFront
Входные данные
4
1
2
3
0
Выходные данные
pushStack
pushQueue
pushFront
3 popStack popQueue popFront