Електрички#4849
На вокзалі є тупиків, куди прибувають електрички. Ця станція є їхньою кінцевою, тому електрички, прибувши, можуть деякий час стояти на вокзалі, а потім відправитися у новий рейс (у напрямку, з якого прибули).
Дано розклад руху, в якому вказано події прибуття та відбуття кожної з електричок у хронологічному порядку. Оскільки вокзал — кінцева станція, електричка, яка прибуває раніше за іншу, може відправитися назад значно пізніше.
Тупики пронумеровані числами від до . Коли електричка прибуває, її ставлять у вільний тупик з мінімальним номером.
Напишіть програму, яка за заданим розкладом для кожної електрички визначить номер тупика, куди її поставлять по прибутті.
У першому рядку знаходиться кількість тупиків (1 \leq k \leq 20000). Далі йдуть рядки, які описують події прибуття та відбуття електричок. Кожна електричка задається своєю протилежною кінцевою станцією — рядком довжиною не більше латинських літер та знаків підкреслення. Подія +city означає, що прибуває електричка з міста , подія -city — що ця електричка відправляється назад у місто . Загальна кількість електричок не перевищує ; для кожної електрички присутні обидві події.
Вважається, що в початковий момент часу всі тупики на вокзалі вільні.
Виведіть по одному числу для кожної електрички — номер тупика, куди її поставлять по прибутті, у порядку надходження подій прибуття. Якщо у якийсь момент тупиків виявиться недостатньо для організації руху електричок за розкладом, виведіть два значення: спочатку , потім назву міста першої електрички, яка не зможе прибути на вокзал.
Приклад 1