Задача №112785. Тростник
Блез выращивает тростник. Казалось бы, при чём тут камни? Он посадил тростник в ряд на отрезке от нуля до N в каждой целой координате, включая концы. К сожалению, тростник растет, только если его поливают, иначе без воды он мгновенно умирает. Изначально все тростники не политы и имеют высоту 0.
Каждый день, если тростник полит, он вырастает на один метр. Однако, если один раз забыть полить тростник он увядает и его высота становится равной нулю. И он будет расти снова, только если Блез его польет.
Блез поливает тростники каждый день. На i-ый день Блез поливает тростники с li по ri включительно. После этого он идет наслаждаться видом на поле. Блез походит к тростнику номер gi и восхищается его величиной. До того как Блез дойдёт до gi тростника, тростник успевает вырасти на один метр или завянуть, в зависимости от того полили его сегодня хозяин или нет. Помогите узнать Блезу на тростник какой высоты он будет любоваться каждый день.
В первой строке даны размеры поля N и количество дней M. В следующих M строках находится по три числа, описывающих i-ый день Блеза в поле: li, ri — границы отрезка который полил сегодня Блез, и номер тростника gi, на который в этот день будет любоваться Блез. Гарантируется, что 0 ≤ li, ri, gi ≤ N, li ≤ ri.
Для каждого дня в отдельной строке выведите высоту тростника, которым будет любоваться Блез.
6 10
1 4 1
1 4 4
1 4 3
1 4 5
2 5 1
2 5 2
2 5 5
0 2 0
0 2 2
0 2 3
1
2
3
0
0
6
3
1
9
0
Подзадача 1.
1 ≤ N ≤ 5000, 1 ≤ M ≤ 5000.Решение оценивается в 11 баллов.
Подзадача 2.
1 ≤ N ≤ 109, 1 ≤ M ≤ 5000. Решение оценивается в 35 баллов.
Подзадача 3.
1 ≤ N ≤ 109, 1 ≤ M ≤ 105. Высоты тростников не превосходят 50. Решение оценивается в 21 балл.
Подзадача 4.
1 ≤ N ≤ 109, 1 ≤ M ≤ 105. Решение оценивается в 33 балла.