Description
Penguin07 is a professional esports player who excels in various games such as “Mobile Legends”, “League of Legends”, “PUBG”, “Fall Guys” and more.
However, his most exceptional game is called the “Counting Game”. In this game, it will provide you with a sequence A of length N and perform M operations with the following rules:
- Given an interval [L,R] and a number X, you are required to add X to all elements of the sequence A in this interval, i.e., Ai (L ≤ i ≤ R)
Please determine the modified sequence after M operations.
Can you, the smartest person in the world, defeat Penguin07 and become the ultimate professional esports player ?
Input
The first line will contain two positive integers, N and M, N is the length of the sequence and M is the number of operations.
The second line contains N integers A1, A2, … , AN, representing the elements of the sequence A.
The following M lines each contain three integers L, R, and X, indicating that you should add X to all elements within the interval [L,R].
Constraints:
- Test Cases 1 ~ 3: 1 ≤ N, M ≤ 103, −109 ≤ A1, A2, ... , AN, X ≤ 109, 1 ≤ L ≤ R ≤ N
- Test Cases 4 ~ 6: 1 ≤ N, M ≤ 106, −109 ≤ A1, A2, ... , AN, X ≤ 109, 1 ≤ L ≤ R ≤ N
Output
Please output N integers, representing the sequence A after performing M operations.
Do not include any spaces at the end of line.
Remember to print a ‘\n’ at the end of the output.
Sample IO Description
- The first operation: A = {2, 3, 3, 4}
- The second operation: A = {2, 5, 5, 4}
- The third operation: A = {2, 5, 9, 8}
So, after performing the three operations, the modified sequence A is: {2, 5, 9, 8}
Hint
How to estimate the running time of your code?
A usual computer can run 109 basic operations (such as +, -, &, |) in 1 second. Although this depends on the judging server, this number serves as a good estimation for the running time of your code. Try to figure out how much operations your code needs to execute to finish all the computations (since not all operations in your code are basic operations, another estimate criterion is 108 operations (+, -, *, /, =, ...) in 1 second)!
If you get WA for testcase 1 ~ 3, you may not have understood what the problem is asking for, or you might have forgotten that the range for int is [-2,147,483,648 ~ 2,147,483,647].
If you get TLE for testcase 4 ~ 6, you should think how to decrease some redundant operations for calculations.
Tags