ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1773. Метро в каждый дом

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Артём — поклонник Екатеринбургского метрополитена. Сейчас он делает ремонт в своей комнате. Артём решил, что одна из стен комнаты будет покрыта белыми обоями, а от левого до правого конца этой стены будет тянуться зелёная линия, напоминающая ему о единственной ветке любимого метро.
Артём подготовил n полос обоев. На каждой полосе он заранее провёл зелёный отрезок от левого до правого края. В каком порядке нужно наклеить эти полосы на стену, чтобы зелёные линии на них образовали один отрезок прямой, тянущийся от левого конца стены до правого?
Для каждой полосы известно расстояние от её нижнего края до концов нарисованного на ней отрезка. Все полосы обоев имеют одинаковую ширину, а их длина равна высоте комнаты Артёма. Перед наклеиванием на стену полосы можно переворачивать вверх ногами.
Problem illustration

Исходные данные

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

Результат

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

Примеры

исходные данныерезультат
5 3
3 2
2 1
2 1
-3 1 2
5 3
3 2
2 1
3 2
0
Автор задачи: Александр Ипатов (подготовка — Марина Мухачёва)
Источник задачи: XIV чемпионат Урала по спортивному программированию, 10 апреля 2010 г.