You are given an array \(A\) having \(N\) integers. You take an array \(B\) of length \(N\) such that \(B_i = 0\) for all \(1 \le i \le N\). You perform \(Q\) operations of the following two types:

\(1 \;L \;R\; X\) : add \(X\) to all elements of the subarray \(A[L \dots R]\)
\(2 \; L\;R\) : add \(A_i\) to \(B_i\) for all \(L \le i \le R\).

Print the elements of the array \(B\) after \(Q\) operations.

Input format

The first line of input contains two integers \(N, Q\) denoting the length of the array \(A\) and the number of operations respectively.
The second line contains \(N\) integers \(A_1, A_2,\dots, A_N\), denoting elements of the array \(A\).
Each of the next \(Q\) lines contains a description of one of the two types of operations.

Output format

Print \(N\) integers \(B_1, B_2,\dots, B_N\), denoting elements of the array \(B\) after \(Q\) operations.

Constraints

\(1 \leq N, Q \leq 2\cdot 10^5\\ 1\le A_i,X\le 10^5\\ 1 \le L_i \le R_i \le N\)