Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Поселения на Арракисе расположены вокруг пустыни и пронумерованы числами от 1 до `N`.
В `i`-й день гигантский песчаный червь появляется в поселении `L_i` и движется в поселение `R_i` (`R_i>=L_i`),
разрушая здания в каждом поселении на своём пути.
В поселении `L_i` червь уничтожает одно здание, в поселении `(L_i+1)` -- 2 здания `(L_i+2)` -- 3 здания и так далее, постепенно увеличивая на 1 количество разрушенных зданий, в
поселении `R_i` червь уничтожит `(R_i-L_i+1)` здание.
Вычислите, сколько зданий будет разрушено после `M` дней.
В первой строке ввода содержится два целых числа -- количество поселений `N` (`1<=N<=100000`) и
количество дней `M` (`1<=M<=100000`). Далее следует `M` строк, в каждой строке два целых числа `L_i` и `R_i` (`1 <= L_i<=R_i<=N`) -- диапазон
номеров поселений, в которых червь разрушает здания.
Вывести `N` целых чисел -- `j`-е число соответствует количеству разрушенных зданий в `j`-м поселении
после `M` дней.
```sample Пример ввода
5 3
1 3
1 2
4 5
```
```sample Пример вывода
2 4 3 1 2
```
Пояснение к примеру: после 1-го дня будет разрушено (1,2,3,0,0) зданий,
после 2-го - (2,4,3,0,0), после 3-го - (2,4,3,1,2).
Начало
Рабочее место участника
Сокращение перебора с помощью идеи