UTS Open '21 P5 - State Taxes

View as PDF

Points: 17 (partial)
Time limit: 2.0s
Java 4.0s
Memory limit: 256M

Author:
Problem type

In the land of UTS, the government has started to automate the taxes of their citizens. To function properly, this automated system needs to know the total revenue of every citizen by the end of the year. As such, the government has hired you to figure this out for them!

At the start of the year, the citizens of UTS numbered from to each start out with a specific salary . A poorly conducted citizen could even have a negative salary! During the year, there are operations of salary changes or payments. On each salary change, all the citizens numbered from to have their salaries increased by . On each payment, all the citizens numbered from to receive their salaries as revenue.

Please help the government find the total revenue of each citizen by the end of the year.

Constraints

For this problem, you MUST pass the sample case in order to receive points. In addition, you must pass all previous subtasks to earn points for a specific subtask.

Input Specification

The first line of input contains integers and , the number of citizens and the number of operations.

The next line of input contains integers , the initial salary of each citizen.

The next lines will be either of the following two forms:

1. indicating that the salaries of the citizens numbered from to increased by .

2. indicating that the citizens numbered from to received their salaries as revenue.

Output Specification

Output space separated integers, with the integer being the total revenue of the citizen by the end of the year.

Sample Input

5 5
1 -3 7 4 2
1 2 3 -2
2 3 4
1 1 5 3
2 3 5
2 1 5

Sample Output

4 -2 21 18 10

Explanation

Initially, the list of salaries is and the list of revenues is .

In the first operation, the citizens in the range have their salaries reduced by . The list of salaries is now .

In the second operation, the citizens in the range receive their salaries as revenue. The list of revenues is now .

In the third operation, the citizens in the range have their salaries increased by . The list of salaries is now .

In the fourth operation, the citizens in the range receive their salaries as revenue. The list of revenues is now .

In the fifth operation, the citizens in the range receive their salaries as revenue. The list of revenues is now .

At the end of the year, the list of revenues is , which is our desired result.