Ватсону поставили задачу размещения пациентов по палатам в больнице. В палате больницы \textbf{N} мест, которые расположены в ряд и пронумерованы от входа последовательно от \textbf{1} до \textbf{N}. Чтобы минимизировать заболеваемость пациентов их нужно размещать как можно дальше друг от друга или от входа, при этом запрещено перемещать их. Ватсону доступен журнал поступления и выписывания пациентов. Для каждого поступления Ватсон должен выдать место, куда следует поместить нового пациента. Для этого необходимо выбрать место, наиболее удаленное от других пациентов в больнице. Если их несколько -- минимизировать количество пациентов, которые находятся наиболее близко к новому пациенту. Если и при этом возникает несколько вариантов, то нужно выбрать самое дальнее от входа место. \InputFile В первой строке указано два целых числа: \textbf{N} -- количество мест в палате и \textbf{Q} -- количество записей в больничном журнале. Далее \textbf{Q} строк, в каждой из которых запись из журнала: "\textbf{0}" -- поступление, "\textbf{1 X}" - выписывание пациента, поступившего по записи в журнале под номером \textbf{X} (нумерация в журнале идет с \textbf{1} и включает как поступления, так и выписывания). Гарантируется нахождение этого пациента в больнице. Также гарантируется, что место в больнице для нового больного всегда найдется. \textbf{0} ≤ \textbf{N}, \textbf{Q} < \textbf{10^5}. \OutputFile Вывести место для каждого поступления по журналу.