Задача "В дек!"

Реализуйте аналогичные очереди процедуры, реализующие дек, и на их основе напишите нижеописанную программу.

В процедуры добавления элемента с дек и извелечения элемента из дека полезно добавить параметр a, имеющий следующий смысл:

• если a=0, то элемент добавляется/извлекается из начала дека
• если a=1, то элемент добавляется/извлекается из конца дека

С помощью дека реализуйте следующий диалог. На вход программе подается последовательность пар чисел. Первое число каждой пары равно 0 или 1 и означает, с какого конца дека выполяется операция (см. описание параметра a выше). В зависимости от второго числа происходит следующее:

• если число положительное, то оно помещается в дек, на выход программы печатается 0,
• если число 0, то, если дек не пуст, из него извлекается стоящее там число и печатается на выход программы, если же дек пуст, печатается -1.

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

Сначала подается число N - количество чисел в последовательности (1≤N≤100). Далее подаются N пар чисел, (первое число пары - 0 или 1, второе число - целое, неотрицательное, не превышающее 1000).

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

На выход должно быть напечатано N чисел, полученных по вышеописанным правилам.

Примеры

Пример ввода	Пример вывода
7 0 1 1 0 0 2 0 3 1 0 0 0 0 0	0 1 0 0 2 3 -1
8 0 1 1 2 0 3 1 4 0 0 0 0 0 0 0 0	0 0 0 0 3 1 2 4