Given an array A of n integers, they are initially 0.
Given q queries of form (l,r,d), increase the value of Ai for all i that satisfy l≤i≤r and (i−l)modd=0 by i−ld+1, where mod 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 i−ld+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≤n,q≤105.
- 1≤l,r,d≤n.
### Example
Input:
52152223
Output:
11203
