Василий очень любит сидеть в телефоне во время поездок в метро, и очень не любит, когда кто-то из соседей видит, чем он занимается в интернете. Вася уверен, что не единственный страдает от такой проблемы, поэтому попросил вас помочь всем любителям посидеть в одиночестве.

Рассмотрим вагон метро, в котором есть один ряд из $$$n$$$ мест, пронумерованных от $$$1$$$ до $$$n$$$, изначально все места свободны. Поступает $$$k$$$ последовательных запросов. Запросы бывают двух типов:

1. «$$$-x$$$». Ушёл пассажир, который вошёл $$$x$$$-м. Гарантируется, что такой пассажир есть в вагоне.
2. «$$$+$$$». Пришел новый пассажир. Гарантируется, что есть хотя бы одно свободное место.

На каждый запрос второго типа следует вывести такой номер свободного места, что расстояние до ближайшего занятого — максимально. Если таких мест несколько, следует вывести место с минимальным номером. Начиная со следующего запроса это место считается занятым, до тех пор, пока его не освободят.