Вибір печива
Як головний програміст на заводі з виробництва печива, ви маєте безліч обов'язків. Один із них полягає в тому, щоб виробництво та упаковка печива відповідали суворим стандартам якості пакувального консорціуму.
У будь-який момент ваша виробнича лінія виготовляє нове печиво, яке зберігається в зоні очікування упаковки. Час від часу надходять запити від пакувального пристрою: передати печиво з зони очікування на упаковку. Ви налаштували систему так, щоб запити на упаковку ніколи не надходили, коли зона очікування порожня. Ситуацію ускладнює те, що представники бюро стандартизації можуть несподівано перевірити, чи відповідає ваше печиво чинним стандартам. Під час такої інспекції вони вимагають, щоб найближчі кілька печив відправлялися на пакувальну машину, а не передавалися їм. Якщо вони переконаються, що ці печива мають потрібний вигляд (і смак), ви пройдете інспекцію, інакше — ні.
На щастя, завод інвестував у нову вимірювальну систему, здатну вимірювати діаметр печива з точністю до 1 нанометра (нм). Оскільки ви не можете постійно чекати інспекторів, ви вирішили, що розумною стратегією для проходження перевірок буде завжди передавати за запитом пакувальної машини печиво, яке має медіанний діаметр серед усього печива, що знаходиться в зоні очікування. Якщо в зоні очікування немає печива з медіанним діаметром, ви можете відправити на упаковку найменше печиво, більше середнього, сподіваючись, що воно задовольнить інспекторів. Упорядкуємо печиво за зростанням діаметра. Якщо непарна кількість c печив знаходиться в зоні очікування, то на упаковку ви відправите те, яке знаходиться в позиції (c + 1) / 2 відсортованої послідовності. Якщо в зоні очікування знаходиться парна кількість c печив, то на запит упаковки відправляється печиво в позиції (c / 2) + 1 відсортованої послідовності.
Вхідні дані
Кожен рядок містить або додатне ціле число d, яке вказує діаметр щойно спеченого печива в нм, що прибуло в зону очікування, або символ #, що вказує на запит пакувальної машини відправити їй одне печиво. Вхідні дані містять не більше 600000 рядків, вважайте зону очікування порожньою перед тим, як у неї прибуде перше печиво. Ви також знаєте, що на заводі не виготовляються печива з діаметром більше 30 сантиметрів (см) (або 300000000 нм).
Вихідні дані
Виведіть послідовність рядків — діаметри в нм печив у порядку, в якому вони відправляються на упаковку.