Выбор печенья
Как у главного программиста на заводе по производству печенья, у Вас имеется много обязанностей. Одна из них состоит в том, чтобы производство и упаковка печенья придерживалась очень строгих стандартов качества упаковочного консорциума.
В каждый момент времени Ваша производственная линия производит новое печенье, которое хранится в зоне ожидания упаковки. Время от времени приходят также запросы от упаковочного устройства: передать печенье из зоны ожидания на упаковку. Естественно, Вы запрограммировали систему таким образом, чтобы никогда не поступали запросы на упаковку при пустой зоне ожидания. Работу усложняет тот факт, что представители бюро стандартизации могут совершить неожиданную проверку - действительно ли Ваше печенье соответствует действующим стандартам. При такой инспекции ее представители требуют, чтобы ближайшие несколько печений отправлялись на упаковочную машину, а не передавались им. Если они убедятся, что эти печенья имеют требуемый вид (и вкус), то Вы прошли инспекцию, в противном случае нет.
К счастью, завод инвестировал в новую измерительную систему, способную измерить диаметр печенья с точностью 1 нанометр (нм). Так как у Вас нет возможности находиться в постоянном ожидании инспекторов печенья, Вы решили, что разумной стратегией справиться с проверками будет всегда передавать по запросу упаковочной машины такое печенье, которое имеет медианный диаметр среди всего печенья, находящегося в настоящее время в зоне ожидания. Если в зоне ожидания отсутствует печенье медианного диаметра, то Вы можете отправить на упаковку наименьшее печенье, больше среднего, надеясь, что оно обрадует прибывших инспекторов. Упорядочим печенье по возрастанию диаметра. Если нечетное количество c печений находится в зоне ожидания, то на упаковку Вы отправите то, которое находится в позиции (c + 1) / 2 отсортированной последовательности. Если в зоне ожидания находится четное количество c печений, то на запрос упаковки отправляется печенье в позиции (c / 2) + 1 отсортированной последовательности.
Входные данные
Каждая строка содержит либо положительное целое d, указывая диаметр только что спеченного печенья в нм прибывшего в зону ожидания, либо символ #, указывая на запрос упаковочной машины отправить ей одно печенье. Входные данные содержат не более 600000 строк, считайте зону ожидания пустой перед тем как в нее прибудет первое печенье. Вы также откуда-то обнаружили, что на заводе не изготовляются печенья с диаметром больше 30 сантиметров (см) (или 300000000 нм).
Выходные данные
Выведите последовательность строк - диаметры в нм печений в порядке, отправляемых на упаковку.