Задача №113564. Кто это кинул?
Одна очень известная корпорация проводит испытания новой модели собакоподобных роботов. Для этого главный инженер этой компании приобрёл бесконечную прямую в магазине «Всё для новорожденных» и положил по палке в каждой целочисленной точке этой прямой. Кроме того на прямой находится n роботов ( 1 ≤ n ≤ 2·10 5 ). Так как у инженера плохое зрение, он не поставит робота на позицию, больше чем m ( 1 ≤ m ≤ 2·10 5 ). Для каждого робота известна его позиция на прямой x i — (целое число, 1 ≤ x i ≤ m ).
Инженер хочет провести эксперимент по поиску палок роботами. Для этого он по очереди даёт роботам команду находить палку. Порядок выдачи команд инженер определяет сам. После получения команды робот начинает двигаться вправо (по направлению увеличения координаты) до тех пор, пока не найдёт палку (если в точке с роботом уже есть палка, то он останется на месте) и забирает её. Инженер очень жалеет милых собак-роботов, поэтому отдаёт им команды в таком порядке, чтобы суммарное расстояние, пройденное роботами было минимальным .
Роботы-собаки очень нежные и ленивые существа, поэтому готовы приносить палки только в определённое время суток. Условно разобьём сутки на k моментов ( 1 ≤ k ≤ 2·10 5 ), тогда робот с номером i выполнит команду, только если она поступила в момент времени не раньше l i и не позже r i ( 1 ≤ l i ≤ r i ≤ k ). В другие моменты времени собака просто останется на месте и не возьмёт палку даже если она находится прямо перед ней.
Главный инженер компании ещё не выбрал время проведения эксперимента. Для каждого момента времени от 1 до k сообщите какое минимальное суммарное расстояние преодолеют роботы, готовые работать в это время, если инженер выберет порядок отдачи команд оптимально.
В первой строке входного файла заданы 2 целых числа n , m и k — количество роботов, максимально допустимая позиция и моментов времени, соответственно.
В последующих n строках дано описание роботов.
В строке i + 1 заданы 3 целых числа l i , r i и x i — минимальный и максимальный момент времени, в который робот с номером i будет работать и его позиция на прямой.
Выведите k целых чисел — ответ на задачу для каждого момента времени от 1 до k .
n , m , k ≤ 5 — 10 баллов.
n , m , k ≤ 5 000 — 40 баллов.
n , m , k ≤ 2·10 5 — 100 баллов.
2 2 2 1 2 1 1 2 1
1 1