Sparse update - MarisaOJ: Marisa Online Judge

Sparse update

Time limit: 1000 ms
Memory limit: 512 MB
Given an array $A$ of $n$ integers, they are initially $0$. Given $q$ queries of form $(l, r, d)$, increase the value of $A_i$ for all $i$ that satisfy $l \le i \le r$ and $(i - l) \bmod d = 0$ by $\frac{i-l}{d}+1$, where $\bmod$ is the modulo operator. This would mean that we only increase the values of $A$ at indices $i$ that are $d$ units apart within the range $[l, r]$ by $\frac{i-l}{d}+1$. Print the array $A$ after $q$ queries. ### Input - The first line contains two integers $n, q$. - The next $q$ lines, each line contains three integers $l, r,d$. It is guaranteed that $r -l$ is divisible by $d$. ### Output - Print the array $A$. ### Constraints - $1 \le n,q \le 10^5$. - $1 \le l, r, d \le n$. ### Example Input: ``` 5 2 1 5 2 2 2 3 ``` Output: ``` 1 1 2 0 3 ```