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 4 3
```
Output:
```
1 1 2 0 3
```
