Задача Парковка

Описание

Администрация города в связи с резким увеличением потока туристов решила организовать в центре города автомобильную стоянку. Стоянка имеет вид кольца с N парковочными местами. Парковочные места занумерованы от 1 до N по часовой стрелке. Автомобилист, подъезжая к стоянке, двигается вдоль нее по часовой стрелке, пока не найдет свободное парковочное место. После этого он паркует свой автомобиль на этом месте. Вчера, после открытия, стоянку посетило M автомобилистов. Про каждого автомобилиста известно время его подъезда к стоянке, время, когда он покинул свою стоянку, а также парковочное место, около которого он подъехал к стоянке. Требуется определить для каждого автомобилиста номер парковочного места, которое он занял. Известно, что никакие два события не произошли одновременно, в частности, никакие два автомобилиста не подъезжают к парковке одновременно, и пока некоторый автомобилист ищет место для парковки, ни один другой автомобилист не подъезжает к парковке и не покидает ее.

Формат входных данных

Первая строка входного файла содержит числа N – количество парковочных мест и M – количество автомобилистов (1 <= N <= 10^5, 1 <= M <= N). Следующие M строк содержат описания автомобилистов в следующем формате: t1 – время подъезда к стоянке, t2 – время, когда он покинул стоянку, и c – номер парковочного места, около которого он подъехал к стоянке (t1, t2 целые, 1 <= t1 < t2 <= 10^9; 1 <= c <= N).

Формат выходных данных

Выведите в выходной файл M чисел – для всех автомобилистов в порядке их перечисления во входном файле выведите номер занятого парковочного места.