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

Артём подготовил n полос обоев. На каждой полосе он заранее провёл зелёный отрезок от левого до правого края. В каком порядке нужно наклеить эти полосы на стену, чтобы зелёные линии на них образовали один отрезок прямой, тянущийся от левого конца стены до правого?

Для каждой полосы известно расстояние от её нижнего края до концов нарисованного на ней отрезка. Все полосы обоев имеют одинаковую ширину, а их длина равна высоте комнаты Артёма. Перед наклеиванием на стену полосы можно переворачивать вверх ногами.

В первой строке через пробел записаны целые числа h и n (1 ≤ h ≤ 100000; 1 ≤ n ≤ 50000) — высота комнаты Артёма и количество заготовленных полос обоев. В i-й из следующих n строк через пробел записаны целые числа l и r (0 ≤ l, r ≤ h), задающие расстояние от нижнего края полосы до левого и правого края нарисованного на ней зелёного отрезка.

Выведите через пробел n чисел — номера полос в том порядке, в котором их следует наклеить на стену. Полосы следует выдавать в порядке от самой левой к самой правой. Если полосу необходимо перевернуть перед наклеиванием, выведите перед её номером минус. Полосы занумерованы числами от 1 до n в том порядке, в котором они описаны на входе. Если есть несколько возможных ответов, выведите любой. Если наклеить обои требуемым образом не удастся, выведите «0».