Statement
You are observing the traffic in front of your house for N seconds now. You have noted down your observations. Each car starts with some initial speed U_i with some constant acceleration A_i at the $L_i$th second and stops in the $R_i$th second. The \text{total speed} at some particular second is the sum of all the speeds of cars at that particular second. Note that cars may start with any U and stop in any V abruptly. For each second from 1 to N, calculate the total speed for each second. Acceleration is constant but the curve isn’t smooth, i.e, the speed increases abruptly at the start of a second and remains the same throughout the second.
Input Format
The first line of input will contain and integer N and M, denoting the number of seconds and number of cars respectively. Likes 2 to N+1 each contain U_i A_i L_i R_i in the same order given denoting the initial speed, accelration per second(Increase in speed per second), start time and stop time for the i th.
Output Format
Print N integers where the i th integer contains the \text{total speed} in the i th second.
Constraints
1 \leq N \leq 10^6
1 \leq M \leq 10^5
1 \leq U_i, A_i, L_i, R_i \leq 10^9
Example
Input: 10 3 1 1 1 10 2 2 1 3 1 3 5 7 Output: 3 6 9 4 6 10 14 8 9 10
Solution Explanation
We can use the idea of “Prefix Sums” here. What we did in prefix sums is store the sum till i in an array and find the sum of a subsegment. Here, we can do something uncannily similar: In another array, we store the change in the variable we need.
First lets solve a easier version of this problem to get a better hold of what I am talking about:
Given an array of size N, and Q number of queries where each query gives a L, R and Val, you need to increase all the elements from index L to R with the value Val, and in the end after all queries are executed, print all the elements.
The O(NQ) solution is pretty trivial here and is just an implementation task but there is a O(N+Q) solution. Take another array, lets call it C. For any L and R you need to you need to add Val to C[L] and subtract Val from C[R+1]. You may still wonder why. Lets take an example.
Suppose I give you an array of 6 elements initially all 0 and then I do one query where L = 2, R = 4, Val = 2. So out array will become
But whats the point?! The point is that, now if we take a variable and traverse this array, we get the elements! Lets take a variable say X and we take a loop from 1 to 6 and we do this:
and also print X in each iteration. What will be the output? Wont it be 0, 2, 2, 2, 0, 0? And isn’t that exactly what we wanted?
Why does this happen? This is because we add 2 in position 2 and then subtract 2 in position 5 to X. You can try doing more queries and dry run this logic to get the result everytime.
Now coming to the original problem, we can do the same thing that we wanted here but in this case we will need two arrays, one to keep track of the change in total speed and one to keep track of change in total acceleration(Does “total acceleration” make sense here?). In the speed array(say V), we will add U_i to position L_i and subtract U_i+A_i \times (R_i-L_i) from position R_i+1. In the acceleration array(say A), we will add A_i to position L_i and subtract A_i from position R_i+1. We will need two variables Total\_speed and Total\_acceleration to keep track of my total speed and acceleration in the current iteration and then do the following to change it according to our problem
And then just print Total\_speed to get the desired result.
I hope you liked this problem. 
If you have any kind of doubts, you can ask here in the comments or you can discuss with others in the WhatsApp group. Do not be shy, we ARE supposed to help each other learn.