E. Стоянка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Автомобильная стоянка в городе N представляет собой n парковочных мест, расположенных в ряд. Парковочные места пронумерованы от 1 до n слева направо.

Когда автомобилист приезжает на стоянку, дежурный определяет для него свободное парковочное место. В целях безопасности выбранное место должно находиться как можно дальше от уже занятых мест, то есть самое близкое занятое парковочное место должно быть как можно дальше. Если таких мест несколько, то среди них выбирается место с наименьшим номером. Если все места на стоянке свободны, то автомобилист получает парковочное место с номером 1.

Считается, что расстояние между i-м и j-м парковочными местами равно 4·|i - j| метров.

Вам заданы записи о приезде на стоянку и отъезде со стоянки автомобилистов в хронологическом порядке. Для каждой записи о приезде автомобилиста, выведите номер выделенного для него парковочного места.

Входные данные

В первой строке записаны через пробел два целых числа n и m (1 ≤ n, m ≤ 2·105) — количество парковочных мест и количество записей соответственно.

В следующих m строках заданы описания записей, одна запись в строке. В i-й строке даны числа ti, idi (1 ≤ ti ≤ 2; 1 ≤ idi ≤ 106). Если ti равно 1, то соответствующая запись информирует о приезде автомобилиста с номером idi на стоянку. Если ti равно 2, то соответствующая запись информирует об отъезде автомобилиста с номером idi со стоянки.

Записи о приезде на стоянку и об отъезде со стоянки автомобилистов заданы в хронологическом порядке. Все события происходили последовательно, никакие два события не происходили одновременно.

Гарантируется, что все записи корректны:

  • каждый автомобилист не более одного раза приезжал на стоянку и не более одного раза уезжал со стоянки,
  • не бывает записи об отъезде автомобилиста, который еще не приехал на стоянку,
  • автомобилистов на стоянке не более n в любой момент времени.

Считайте, что автомобилистам присвоены произвольные номера от 1 до 106, все присвоенные номера — различны. Первоначально все парковочные места на стоянке свободны.

Выходные данные

Для каждой записи о приезде автомобилиста, выведите номер выделенного для него парковочного места. Номера выделенных мест выводите в порядке приезда автомобилистов на стоянку.

Примеры
Входные данные
7 11
1 15
1 123123
1 3
1 5
2 123123
2 15
1 21
2 3
1 6
1 7
1 8
Выходные данные
1
7
4
2
7
4
1
3