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 $N$ citizens of UTS numbered from $1$ to $N$ each start out with a specific salary $a_i$. A poorly conducted citizen could even have a negative salary! During the year, there are $Q$ operations of salary changes or payments. On each salary change, all the citizens numbered from $l_i$ to $r_i$ have their salaries increased by $x_i$. On each payment, all the citizens numbered from $l_i$ to $r_i$ 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.

For all subtasks:

$1\le N,Q\le 5\times {10}^5$

$1\le l_i\le r_i\le N$

$-{10}^8\le a_i,x_i\le {10}^8$

Subtask 1 [10%]

$1\le N,Q\le {10}^3$

Subtask 2 [90%]

No additional constraints.

Input Specification

The first line of input contains $2$ integers $N$ and $Q$, the number of citizens and the number of operations.

The next line of input contains $N$ integers $a_i$ $(1\le i\le N)$, the initial salary of each citizen.

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

1. $1$ $l_i$ $r_i$ $x_i$ indicating that the salaries of the citizens numbered from $l_i$ to $r_i$ increased by $x_i$.

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

Output Specification

Output $N$ space separated integers, with the $i^{\text{th}}$ integer being the total revenue of the $i^{\text{th}}$ 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 $[1,-3,7,4,2]$ and the list of revenues is $[0,0,0,0,0]$.

In the first operation, the citizens in the range $[2,3]$ have their salaries reduced by $2$. The list of salaries is now $[1,-5,5,4,2]$.

In the second operation, the citizens in the range $[3,4]$ receive their salaries as revenue. The list of revenues is now $[0,0,5,4,0]$.

In the third operation, the citizens in the range $[1,5]$ have their salaries increased by $3$. The list of salaries is now $[4,-2,8,7,5]$.

In the fourth operation, the citizens in the range $[3,5]$ receive their salaries as revenue. The list of revenues is now $[0,0,13,11,5]$.

In the fifth operation, the citizens in the range $[1,5]$ receive their salaries as revenue. The list of revenues is now $[4,-2,21,18,10]$.

At the end of the year, the list of revenues is $[4,-2,21,18,10]$, which is our desired result.