23. Гоблины и шаманы

Гоблины Мглистых гор очень любят ходить к своим шаманам. Так как гоблинов много, к шаманам часто образуются очень длинные очереди. А поскольку много гоблинов в одном месте быстро образуют шумную толпу, которая мешает шаманам проводить сложные медицинские манипуляции, последние решили установить некоторые правила касательно порядка в очереди.

Обычные гоблины при посещении шаманов должны вставать в конец очереди. Привилегированные же гоблины, знающие особый пароль, встают ровно в её середину, причем при нечётной длине очереди они встают сразу за центром.

Так как гоблины также широко известны своим непочтительным отношением ко всяческим правилам и законам, шаманы попросили вас написать программу, которая бы отслеживала порядок гоблинов в очереди.

В первой строке входных данный записано число N ($1 \le N \le 10^{5}$) — количество запросов к программе. Следующие N строк содержат описание запросов в формате:

''+ i'' — гоблин с номером i ($1 \le i \le N$) встает в конец очереди.

''* i'' — привилегированный гоблин с номером i встает в середину очереди.

''-'' — первый гоблин из очереди уходит к шаманам. Гарантируется, что на момент такого запроса очередь не пуста.

Для каждого запроса типа ''-'' программа должна вывести номер гоблина, который должен зайти к шаманам.