Problem J
Vildsvin
Lovisa har en väldigt stor trädgård som hon gillar väldigt mycket. Tyvärr gillar vildsvin också trädgården väldigt mycket. De senaste dagarna har $V$ stycken vildsvin bökat i den. Vildsvinen gillar en särskild remsa som innehåller $N$ stycken $1 \times 1$-rutor, numrerade från $0$ till $N-1$. Varje gång ett vildsvin kommer och bökar så gräver det upp $k$ enheter jord från varje ruta i ett intervall $l$ till $r$.
Till exempel, anta att $N=6$. Ovanför varje ruta står det hur mycket jord som grävts upp vid den rutan. Då ser hennes trädgård ut såhär till en början.
![\includegraphics[scale=0.6]{1-1.png}](/problems/vildsvin/file/statement/sv/img-0001.png)
Sen kommer ett vildsvin och gräver upp $k=1$ enheter jord från rutorna $l=1$ till $r=3$. Varje ruta i bilden nedan representerar en enhet uppgrävd jord.
![\includegraphics[scale=0.6]{1-2.png}](/problems/vildsvin/file/statement/sv/img-0002.png)
Om det senare kommer ett till vildsvin som gräver $k=2$ enheter jord från rutorna $l=2$ till $r=5$ ser trädgården ut såhär:
![\includegraphics[scale=0.6]{1-3.png}](/problems/vildsvin/file/statement/sv/img-0003.png)
Lovisa är nu väldigt nyfiken över hur djupt hålet är. Tyvärr är det så djupt att hon inte kan se botten av det. Som tur är har hon antecknat $l$, $r$ och $k$ för alla de $V$ stycken vildsvinen som har bökat i hennes trädgård. Kan du hjälpa henne avgöra hur många enheter jord som grävts upp från varje ruta?
Indata
På första raden av indata står två heltal $N$ och $V$ ($1 \leq N, V \leq 2 \cdot 10^5$), antalet rutor i remsan och antalet vildsvin som bökat i Lovisas trädgård.
De följande $V$ raderna beskriver hur vilsvinen bökade i trädgården. Varje rad beskriver ett vildsvin med heltalen $l$, $r$ och $k$ ($0 \leq l \leq r < N$, $1 \leq k \leq 1000$), som betyder att vildsvinet grävde upp $k$ enheter jord från rutorna numrerade $l,l+1, \dots , r$.
Utdata
Skriv ut hur mycket jord som grävts upp från varje ruta
efter att alla vildsvin är färdiga.
För varje ruta, skriv ut hur många enheter jord som grävts upp
från den, separerade av mellanslag. Skriv först ut antalet
enheter jord för ruta 0, sen ruta 1 och så vidare.
Poängsättning
Din lösning kommer att testas på två olika testgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.
|
Grupp |
Poäng |
Gränser |
|
$1$ |
$40$ |
$N, V \leq 1000$ |
|
$2$ |
$60$ |
Inga ytterligare begränsningar. |
Förklaring av exempelfall 1
Se bilderna ovanför, som beskriver trädgården efter det att inget, det första och det andra vildsvinet bökat runt.
| Sample Input 1 | Sample Output 1 |
|---|---|
6 2 1 3 1 2 5 2 |
0 1 3 3 2 2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 3 0 0 2 4 4 3 0 4 10 |
12 10 10 10 13 |
